2004
Journal article
Open Access
Composing event constraints in state-based specification
Bolognesi T.
Event-based process algebraic specification languages support an elegant specification technique by which system behaviours are described as compositions of constraints on event occurrences and event parameters. This paper investigates the possibility to export this specification paradigm to a state-based formalism, and discusses some deriving advantages in terms of verification.Source: Lecture notes in computer science 3235 (2004): 13–32. doi:10.1007/978-3-540-30232-2_2
DOI: 10.1007/978-3-540-30232-2_2
Metrics:
Bolognesi T.
Event-based process algebraic specification languages support an elegant specification technique by which system behaviours are described as compositions of constraints on event occurrences and event parameters. This paper investigates the possibility to export this specification paradigm to a state-based formalism, and discusses some deriving advantages in terms of verification.Source: Lecture notes in computer science 3235 (2004): 13–32. doi:10.1007/978-3-540-30232-2_2
DOI: 10.1007/978-3-540-30232-2_2
Metrics:
See at:
link.springer.com 
| www.springerlink.com | doi.org 
| CNR ExploRA
2007
Journal article
Open Access
Behavioral complexity indicators for process algebra: the NKS approach
Bolognesi T.
Several techniques for the experimental investigation of the computing power of various formal models, from cellular automata to Turing machines, have been proposed by S.Wolfram with his NKS (New Kind of Science). Visual complexity indicators reveal the 'internal shapes' of computations, and may expose constant, periodic, nested/fractal, pseudo-random, and even more sophisticated dynamics. In this paper we investigate visual complexity indicators for process algebra. With its emphasis on reactive, continuously observable behavior, as opposed to input/output behavior, process algebra might appear as an ideal candidate for NKS-style investigations; however, this formal model is in some sense more elaborate than the simple formalisms addressed in NKS, and poses specific problems, such as the presence of both events and states, and the explosive nature of non-determinism. We consider a set of process algebraic operators and prove its Turing universality by showing that they can emulate any elementary cellular automaton, including n. 110, which is itself universal. The correctness of the emulation is supported by an original visual indicator, which is then used for exploring various subclasses of algebraic expressions and their emergent features. Based on this indicator, and even by restricting to deterministic computations, we have detected and measured, by a data compression technique, the emergence of randomness in a subclass of expressions which is provably not universal. Besides providing a suggestive visualization of the relative strengths of operator subsets, we believe that results of this type, both of theoretical and of experimental nature, are desirable in light of one of the key NKS conjectures, according to which random-like behavior would be a witness of computational universality.Source: The journal of logic and algebraic programming 72 (2007): 50–77. doi:10.1016/j.jlap.2007.02.004
DOI: 10.1016/j.jlap.2007.02.004
Metrics:
Bolognesi T.
Several techniques for the experimental investigation of the computing power of various formal models, from cellular automata to Turing machines, have been proposed by S.Wolfram with his NKS (New Kind of Science). Visual complexity indicators reveal the 'internal shapes' of computations, and may expose constant, periodic, nested/fractal, pseudo-random, and even more sophisticated dynamics. In this paper we investigate visual complexity indicators for process algebra. With its emphasis on reactive, continuously observable behavior, as opposed to input/output behavior, process algebra might appear as an ideal candidate for NKS-style investigations; however, this formal model is in some sense more elaborate than the simple formalisms addressed in NKS, and poses specific problems, such as the presence of both events and states, and the explosive nature of non-determinism. We consider a set of process algebraic operators and prove its Turing universality by showing that they can emulate any elementary cellular automaton, including n. 110, which is itself universal. The correctness of the emulation is supported by an original visual indicator, which is then used for exploring various subclasses of algebraic expressions and their emergent features. Based on this indicator, and even by restricting to deterministic computations, we have detected and measured, by a data compression technique, the emergence of randomness in a subclass of expressions which is provably not universal. Besides providing a suggestive visualization of the relative strengths of operator subsets, we believe that results of this type, both of theoretical and of experimental nature, are desirable in light of one of the key NKS conjectures, according to which random-like behavior would be a witness of computational universality.Source: The journal of logic and algebraic programming 72 (2007): 50–77. doi:10.1016/j.jlap.2007.02.004
DOI: 10.1016/j.jlap.2007.02.004
Metrics:
See at:
The Journal of Logic and Algebraic Programming | biblioproxy.cnr.it | CNR ExploRA
2007
Journal article
Unknown
Planar trivalent network computation
Bolognesi T.
Confluent rewrite systems for giant trivalent networks have been investigated by S. Wolfram as possible models of space and spacetime, in the ambitious search for the most fundamental, computational laws of physics. We restrict here to planar trivalent nets, which are shown to support Turing-complete computations, and take an even more radical, approach: while operating on network duals, we use just one elementary rewrite rule and drive its application by a simple, fully deterministic algorithm, rather than by pattern-matching. We devise effective visual indicators for exploring the complexity of computations with elementary initial conditions, consisting of thousands of graphs, and expose a rich variety of behaviors, from regular to random-like. Among their features we study, in particular, the dimensionality of the emergent space.Source: Lecture notes in computer science 4664 (2007): 146–157.
Bolognesi T.
Confluent rewrite systems for giant trivalent networks have been investigated by S. Wolfram as possible models of space and spacetime, in the ambitious search for the most fundamental, computational laws of physics. We restrict here to planar trivalent nets, which are shown to support Turing-complete computations, and take an even more radical, approach: while operating on network duals, we use just one elementary rewrite rule and drive its application by a simple, fully deterministic algorithm, rather than by pattern-matching. We devise effective visual indicators for exploring the complexity of computations with elementary initial conditions, consisting of thousands of graphs, and expose a rich variety of behaviors, from regular to random-like. Among their features we study, in particular, the dimensionality of the emergent space.Source: Lecture notes in computer science 4664 (2007): 146–157.
See at: CNR ExploRA
2003
Conference article
Unknown
Remarks on Turbo ASMs for Functional Equations and Recursion Schemes
Boerger E., Bolognesi T.
The question raised in [15] is answered how to naturally model widely used forms of recursion by abstract machines. We show that turbo ASMs as defined in [7] allow one to faithfully reflect the common intuitive single-agent understanding of recursion. The argument is illustrated by turbo ASMs for Mergesort and Quicksort. Using turbo ASMs for returning function values allows one to seamlessly integrate functional description and programming techniques into the high-level 'abstract programming' by state transforming ASM rules.Source: Abstract State Machines 2003 - Advances in Theory and Practice, pp. 218–228, Taormina, Italy, 3-7 March 2003
Boerger E., Bolognesi T.
The question raised in [15] is answered how to naturally model widely used forms of recursion by abstract machines. We show that turbo ASMs as defined in [7] allow one to faithfully reflect the common intuitive single-agent understanding of recursion. The argument is illustrated by turbo ASMs for Mergesort and Quicksort. Using turbo ASMs for returning function values allows one to seamlessly integrate functional description and programming techniques into the high-level 'abstract programming' by state transforming ASM rules.Source: Abstract State Machines 2003 - Advances in Theory and Practice, pp. 218–228, Taormina, Italy, 3-7 March 2003
See at: CNR ExploRA
2009
Journal article
Restricted
A pseudo-random network mobile automaton with linear growth
Bolognesi T.
Based on the mobile automaton model, an algorithm is introduced that grows planar, tri-valent graphs by exhibiting a peculiar, twofold dynamics. In a first phase, graph growth appears to be pseudo-random and O(n); then it settles to a very regular behavior and O(Sqrt(n)) rate. A pseudo-random O(Sqrt(n)) mobile automaton is already known; the new automaton provides now a finite, but surprisingly long, pseudo-random, linear growth process. Applications of mobile automata to fundamental physics and quantum gravity have been recently suggested.Source: Information processing letters (Print) 109 (2009): 668–674. doi:10.1016/j.ipl.2009.02.023
DOI: 10.1016/j.ipl.2009.02.023
Metrics:
Bolognesi T.
Based on the mobile automaton model, an algorithm is introduced that grows planar, tri-valent graphs by exhibiting a peculiar, twofold dynamics. In a first phase, graph growth appears to be pseudo-random and O(n); then it settles to a very regular behavior and O(Sqrt(n)) rate. A pseudo-random O(Sqrt(n)) mobile automaton is already known; the new automaton provides now a finite, but surprisingly long, pseudo-random, linear growth process. Applications of mobile automata to fundamental physics and quantum gravity have been recently suggested.Source: Information processing letters (Print) 109 (2009): 668–674. doi:10.1016/j.ipl.2009.02.023
DOI: 10.1016/j.ipl.2009.02.023
Metrics:
See at:
biblioproxy.cnr.it | Information Processing Letters | CNR ExploRA
2010
Journal article
Closed Access
Causal sets from simple models of computation
Bolognesi T.
Causality among events is widely recognized as a most fundamental structure of spacetime, and causal sets have been proposed as discrete models of the latter in the context of quantum gravity theories, notably in the Causal Set Programme. In the rather different context of what might be called the 'Computational Universe Programme' -- one which associates the complexity of physical phenomena to the emergent features of models such as cellular automata -- a choice problem arises with respect to the variety of formal systems that, in virtue of their computational universality (Turing-completeness), qualify as equally good candidates for a computational, unified theory of physics. We address this problem by proposing Causal Sets to be the only objects of physical significance under the computational universe perspective. At the same time, we propose a fully deterministic, radical alternative to the probabilistic techniques considered in the Causal Set Programme for growing discrete spacetime instances. We investigate a number of computation models, all operating on a one-dimensional support like a tape or a string of symbols, we identify the causality relation among their computation events, implement it, and conduct a possibly exhaustive exploration of the associated causal set space, while examining quantitative and qualitative features such as dimensionality, curvature, planarity, emergence of pseudo-randomness and particles.Source: International journal of unconventional computing 6 (2010): 489–524.
Bolognesi T.
Causality among events is widely recognized as a most fundamental structure of spacetime, and causal sets have been proposed as discrete models of the latter in the context of quantum gravity theories, notably in the Causal Set Programme. In the rather different context of what might be called the 'Computational Universe Programme' -- one which associates the complexity of physical phenomena to the emergent features of models such as cellular automata -- a choice problem arises with respect to the variety of formal systems that, in virtue of their computational universality (Turing-completeness), qualify as equally good candidates for a computational, unified theory of physics. We address this problem by proposing Causal Sets to be the only objects of physical significance under the computational universe perspective. At the same time, we propose a fully deterministic, radical alternative to the probabilistic techniques considered in the Causal Set Programme for growing discrete spacetime instances. We investigate a number of computation models, all operating on a one-dimensional support like a tape or a string of symbols, we identify the causality relation among their computation events, implement it, and conduct a possibly exhaustive exploration of the associated causal set space, while examining quantitative and qualitative features such as dimensionality, curvature, planarity, emergence of pseudo-randomness and particles.Source: International journal of unconventional computing 6 (2010): 489–524.
See at:
www.oldcitypublishing.com | CNR ExploRA
2004
Journal article
Open Access
Predicates for state changes vs. processes for event patterns
Bolognesi T.
The two informal 'mental landscapes' that provide the intuitive substratum for state- oriented and event-oriented formal specifications are discussed, and abstractly characterised as net- works of constraints. The structuring facilities offered by the two approaches are contrasted. A technique is introduced for expanding an event-oriented specification consisting of a fixed pattern of interacting processes into a state-oriented specification formed by a complex 'action predicate' manipulating a set of state variables. Although by this transformation the event and process con- cepts can be absorbed into the state-based conceptual framework, we discuss some good reasons for regarding these concepts as primitive expressive tools, and for structuring specifications around them.Source: Studia informatica universalis. Hors série 3 (2004): 85–124.
Bolognesi T.
The two informal 'mental landscapes' that provide the intuitive substratum for state- oriented and event-oriented formal specifications are discussed, and abstractly characterised as net- works of constraints. The structuring facilities offered by the two approaches are contrasted. A technique is introduced for expanding an event-oriented specification consisting of a fixed pattern of interacting processes into a state-oriented specification formed by a complex 'action predicate' manipulating a set of state variables. Although by this transformation the event and process con- cepts can be absorbed into the state-based conceptual framework, we discuss some good reasons for regarding these concepts as primitive expressive tools, and for structuring specifications around them.Source: Studia informatica universalis. Hors série 3 (2004): 85–124.
See at:
studia.complexica.net | CNR ExploRA
2008
Journal article
Unknown
Planar trinet dynamics with two rewrite rules
Bolognesi T.
We propose a deterministic network mobile automaton for the creation of planar trivalent networks (trinets) based on the application of only two simple rewrite rules, and we enumerate and explore the possible brownian dynamics of the control point. A useful behavioral complexity indicator is introduced, called revisit indicator, exposing a variety of emergent features, involving periodic, nested and random like dynamics. Regular structures obtained include 1-D graphs, oscillating rings, and the 2-D, hexagonal grid. In two cases only, out of over a thousand we have inspected, a remarkably fair, random-like revisit indicator is found, whose trinets exhibit a slow, square-root growth rate; some properties of these surprising computations are investigated. Finally, one 2-D case is found that seems to be unique in the way regularity and randomness are mixed.Source: Complex systems 18 (2008): 1–41.
Bolognesi T.
We propose a deterministic network mobile automaton for the creation of planar trivalent networks (trinets) based on the application of only two simple rewrite rules, and we enumerate and explore the possible brownian dynamics of the control point. A useful behavioral complexity indicator is introduced, called revisit indicator, exposing a variety of emergent features, involving periodic, nested and random like dynamics. Regular structures obtained include 1-D graphs, oscillating rings, and the 2-D, hexagonal grid. In two cases only, out of over a thousand we have inspected, a remarkably fair, random-like revisit indicator is found, whose trinets exhibit a slow, square-root growth rate; some properties of these surprising computations are investigated. Finally, one 2-D case is found that seems to be unique in the way regularity and randomness are mixed.Source: Complex systems 18 (2008): 1–41.
See at: CNR ExploRA
2004
Conference article
Closed Access
A conceptual framework for state-based and event-based formal behavioural specification languages
Bolognesi T.
We introduce a simple conceptual framework for assessing a number of well known formal specification techniques w.r.t. their ability to model state-oriented and/or event-oriented aspects of system behaviour. By attributing a-priori equal importance to the notions of event and state, by explicitly recognizing the two derived, fundamental ways of thinking about system behaviours, and by assessing the bias of existing formal methods towards one or the other, one can make more conscious choices in the upper phases of software development, that is, in requirements elicitation and analysis, in the construction of abstract system models, and in the choice of formal languages for high- and low-level design. In particular, we assess the recently introduced model of Abstract State Processes, and the design choices behind its definition, in light of the introduced state-event framework.Source: Ninth IEEE International Conference on Engineering of Complex Computer Systems, pp. 107–116, Florence, April 14-16, 2004
DOI: 10.1109/iceccs.2004.1310909
Metrics:
Bolognesi T.
We introduce a simple conceptual framework for assessing a number of well known formal specification techniques w.r.t. their ability to model state-oriented and/or event-oriented aspects of system behaviour. By attributing a-priori equal importance to the notions of event and state, by explicitly recognizing the two derived, fundamental ways of thinking about system behaviours, and by assessing the bias of existing formal methods towards one or the other, one can make more conscious choices in the upper phases of software development, that is, in requirements elicitation and analysis, in the construction of abstract system models, and in the choice of formal languages for high- and low-level design. In particular, we assess the recently introduced model of Abstract State Processes, and the design choices behind its definition, in light of the introduced state-event framework.Source: Ninth IEEE International Conference on Engineering of Complex Computer Systems, pp. 107–116, Florence, April 14-16, 2004
DOI: 10.1109/iceccs.2004.1310909
Metrics:
See at:
doi.org | ieeexplore.ieee.org | CNR ExploRA
2005
Conference article
Closed Access
Process algebra under the light of Wolfram's NKS
Bolognesi T.
The strong intellectual investment behind the definition of process algebras and the high abstraction level they can attain in formal specification still contrasts with their degree of penetration into software engineering practice, but also with the relatively limited number of other fields of fundamental science where these models have played some role. An emerging area in which process algebras might lend themselves to attractive investigations is Wolfram's 'New Kind of Science' (NKS). In this short note we start discussing possible motivations and preliminary steps for placing process algebra under this new light, and for exploring its versatility by NKS-style experiments.Source: Algebraic Process Calculi: The First Twenty Five Years and Beyond, PA '05, pp. 56–59, Bertinoro, August 1-5, 2005
Bolognesi T.
The strong intellectual investment behind the definition of process algebras and the high abstraction level they can attain in formal specification still contrasts with their degree of penetration into software engineering practice, but also with the relatively limited number of other fields of fundamental science where these models have played some role. An emerging area in which process algebras might lend themselves to attractive investigations is Wolfram's 'New Kind of Science' (NKS). In this short note we start discussing possible motivations and preliminary steps for placing process algebra under this new light, and for exploring its versatility by NKS-style experiments.Source: Algebraic Process Calculi: The First Twenty Five Years and Beyond, PA '05, pp. 56–59, Bertinoro, August 1-5, 2005
See at:
www.brics.dk | CNR ExploRA
2002
Conference article
Unknown
Process algebraic operators for ASMs
Bolognesi T., Boerger E.
An abstract is not availableSource: Theory and Application of Abstract State Machines - International Conference and Research Center for Computer Science, Dagstuhl, Germany, 3-8 March 2002
Bolognesi T., Boerger E.
An abstract is not availableSource: Theory and Application of Abstract State Machines - International Conference and Research Center for Computer Science, Dagstuhl, Germany, 3-8 March 2002
See at: CNR ExploRA
2002
Contribution to conference
Unknown
Towards Abstract State Processes
Bolognesi T.
An abstract is not availableSource: FM&&T Day, Pisa, Italy, 2002
Bolognesi T.
An abstract is not availableSource: FM&&T Day, Pisa, Italy, 2002
See at: CNR ExploRA
2014
Journal article
Open Access
Teilhard de Chardin e Wolfram: modelli di universo computazionale ed emergenza del foglietto interno delle cose
Bolognesi T.
The ambitious goal of 'The Human Phenomenon' by Teilhard de Chardin is to describe the Cosmos and its evolution in a way that integrates the outside and the inside of things - the material world and the dimensions of psyche and consciousness - while preserving the character of a scientific investigation. By following the teilhardian steps of Prelife-Life-Though, and by using results that were still largely unknown during Teilhard's lifespan, due, in particular, to Wolfram, Chaitin and Tononi, in this short essay we show that it is possible and useful to try and understand the ultimate fabric of the universe, some phenomena in the biosphere, and the notion of consciousness itself, in terms of the concept of computation, that is, as phenomena emerging from information processing.Source: Studium (Syd.) 110 (2014): 340–360.
Bolognesi T.
The ambitious goal of 'The Human Phenomenon' by Teilhard de Chardin is to describe the Cosmos and its evolution in a way that integrates the outside and the inside of things - the material world and the dimensions of psyche and consciousness - while preserving the character of a scientific investigation. By following the teilhardian steps of Prelife-Life-Though, and by using results that were still largely unknown during Teilhard's lifespan, due, in particular, to Wolfram, Chaitin and Tononi, in this short essay we show that it is possible and useful to try and understand the ultimate fabric of the universe, some phenomena in the biosphere, and the notion of consciousness itself, in terms of the concept of computation, that is, as phenomena emerging from information processing.Source: Studium (Syd.) 110 (2014): 340–360.
See at:
www.edizionistudium.it | CNR ExploRA
2003
Report
Open Access
On state-oriented vs. event-oriented thinking in formal behavioural specifications
Bolognesi T.
In this paper an extension of a behavioural subset of UML Statecharts for modeling mobility issues is proposed. The extension builds on the notion of Multicharts, as proposed by the authors in previous work. A Multichart is a collection of Statecharts, where each Statechart is associated with a unique input queue. In a Multichart each Statechart can address its output events directly to each (other) Statechart of the Multichart by explicitly mentioning the name of (the unique queue of) such Statechart in its output actions. The extension we present consists in relaxing the unique association between each Statechart and its input-queue and in allowing the the use of (queue) name variables in communication actions. The resulting communication paradigm is much more flexible than the standard asymmetric one and is well suited for the modelling of mobility-oriented as well as fault tolerant systems.Source: ISTI Technical reports, 2003
Bolognesi T.
In this paper an extension of a behavioural subset of UML Statecharts for modeling mobility issues is proposed. The extension builds on the notion of Multicharts, as proposed by the authors in previous work. A Multichart is a collection of Statecharts, where each Statechart is associated with a unique input queue. In a Multichart each Statechart can address its output events directly to each (other) Statechart of the Multichart by explicitly mentioning the name of (the unique queue of) such Statechart in its output actions. The extension we present consists in relaxing the unique association between each Statechart and its input-queue and in allowing the the use of (queue) name variables in communication actions. The resulting communication paradigm is much more flexible than the standard asymmetric one and is well suited for the modelling of mobility-oriented as well as fault tolerant systems.Source: ISTI Technical reports, 2003
See at:
ISTI Repository | CNR ExploRA
2006
Report
Open Access
Formalizing uncertainty in service request/offer description and matching
Bolognesi T.
This paper discusses the problem of describing and matching service requests and offers, that appears as central and characteristic in the context of the Service Oriented Computing (SOC) paradigm. Service descriptions, be they requests or offers, are seen as a mix of detailed, local state information, and fuzzy information, or speculation, about remote partners. Service fruition is represented, at a very high abstraction level, as an atomic interaction among two or more parties, each providing a partial view about a global state change. We propose here four formal solutions of increasing complexity; the first three of them are conveniently formalized in TLA+ and illustrated by simple examples. The use of a logic-based approach should favor the integration with current Semantic Web technologies, and with Description Logics, and at the same time it should help reducing the gap between formal and informal (natural language) descriptions of services.Source: ISTI Technical reports, 2006
Bolognesi T.
This paper discusses the problem of describing and matching service requests and offers, that appears as central and characteristic in the context of the Service Oriented Computing (SOC) paradigm. Service descriptions, be they requests or offers, are seen as a mix of detailed, local state information, and fuzzy information, or speculation, about remote partners. Service fruition is represented, at a very high abstraction level, as an atomic interaction among two or more parties, each providing a partial view about a global state change. We propose here four formal solutions of increasing complexity; the first three of them are conveniently formalized in TLA+ and illustrated by simple examples. The use of a logic-based approach should favor the integration with current Semantic Web technologies, and with Description Logics, and at the same time it should help reducing the gap between formal and informal (natural language) descriptions of services.Source: ISTI Technical reports, 2006
See at:
ISTI Repository | CNR ExploRA
2006
Report
Open Access
Planar trivalent network computation
Bolognesi T.
Confluent rewrite systems for giant trivalent networks of unstructured nodes have been investigated by S. Wolfram as possible models of space and spacetime, in the ambitious search for the most fundamental, computational laws of physics. We restrict here to planar trivalent nets, which are shown to support Turing-complete computations, and take an even more radical, approach: while operating on network duals, we use just {em one} elementary rewrite rule -- which is singled out also by Loop Quantum Gravity -- and drive its application by (two variants of) a simple, fully deterministic algorithm, rather than by pattern-matching. We devise effective visual indicators for exploring the complexity of computations with elementary initial conditions, consisting of thousands of graphs, and expose a rich variety of behaviors, from regular to random-like. Among their features we study, in particular, the dimensionality of the emergent space.Source: ISTI Technical reports, 2006
Bolognesi T.
Confluent rewrite systems for giant trivalent networks of unstructured nodes have been investigated by S. Wolfram as possible models of space and spacetime, in the ambitious search for the most fundamental, computational laws of physics. We restrict here to planar trivalent nets, which are shown to support Turing-complete computations, and take an even more radical, approach: while operating on network duals, we use just {em one} elementary rewrite rule -- which is singled out also by Loop Quantum Gravity -- and drive its application by (two variants of) a simple, fully deterministic algorithm, rather than by pattern-matching. We devise effective visual indicators for exploring the complexity of computations with elementary initial conditions, consisting of thousands of graphs, and expose a rich variety of behaviors, from regular to random-like. Among their features we study, in particular, the dimensionality of the emergent space.Source: ISTI Technical reports, 2006
See at:
ISTI Repository | CNR ExploRA
2007
Report
Open Access
See at:
ISTI Repository | CNR ExploRA
2005
Other
Open Access
Introductory paper - Special section on St.Eve workshop
Bolognesi T., Derrick J.
An abstract is not availableDOI: 10.1007/s10270-005-0082-5
Metrics:
Bolognesi T., Derrick J.
An abstract is not availableDOI: 10.1007/s10270-005-0082-5
Metrics:
See at:
ISTI Repository | CNR ExploRA
2008
Report
Open Access
A pseudo-random network mobile automaton with linear growth
Bolognesi T.
Based on the mobile automaton computational paradigm, a (fully deterministic) algorithm is introduced that grows planar graphs while exhibiting surprisingly uniform pseudo-random dynamics. The graph growth rate, as a function of the automaton steps, is O(n), and nicely combines with the O(Sqrt[n]) of a previously introduced algorithm of ours: these two rates are also achieved by two most elementary visit-and-grow procedures with regular dynamics, of which our automata can be viewed as randomized versions. Applications of mobile automata to fundamental physics and quantum gravity have been recently suggested, but other application areas are envisaged as well.Source: ISTI Technical reports, 2008
Bolognesi T.
Based on the mobile automaton computational paradigm, a (fully deterministic) algorithm is introduced that grows planar graphs while exhibiting surprisingly uniform pseudo-random dynamics. The graph growth rate, as a function of the automaton steps, is O(n), and nicely combines with the O(Sqrt[n]) of a previously introduced algorithm of ours: these two rates are also achieved by two most elementary visit-and-grow procedures with regular dynamics, of which our automata can be viewed as randomized versions. Applications of mobile automata to fundamental physics and quantum gravity have been recently suggested, but other application areas are envisaged as well.Source: ISTI Technical reports, 2008
See at:
ISTI Repository | CNR ExploRA
2010
Report
Open Access
Causal sets from simple models of computation
Bolognesi T.
Causality among events is widely recognized as a most fundamental structure of spacetime, and causal sets have been proposed as discrete models of the latter in the context of quantum gravity theories, notably in the Causal Set Programme. In the rather different context of what might be called the 'Computational Universe Programme' -- one which associates the complexity of physical phenomena to the emergent features of models such as cellular automata -- a choice problem arises with respect to the variety of formal systems that, in virtue of their computational universality (Turing-completeness), qualify as equally good candidates for a computational, unified theory of physics. This paper proposes Causal Sets as the only objects of physical significance and relevance to be considered under the 'computational universe' perspective, and as the appropriate abstraction for shielding the unessential details of the many different computationally universal candidate models. At the same time, we propose a fully deterministic, radical alternative to the probabilistic techniques currently considered in the Causal Set Programme for growing discrete spacetimes. We investigate a number of computation models by grouping them into two broad classes, based on the support on which they operate; in one case this is linear, like a tape or a string of symbols; in the other, it is a two-dimensional grid or a planar graph. For each model we identify the causality relation among computation events, implement it, and conduct a possibly exhaustive exploration of the associated causal set space, while examining quantitative and qualitative features such as dimensionality, curvature, planarity, emergence of pseudo-randomness, causal set substructures and particles.Source: ISTI Technical reports, 2010
Bolognesi T.
Causality among events is widely recognized as a most fundamental structure of spacetime, and causal sets have been proposed as discrete models of the latter in the context of quantum gravity theories, notably in the Causal Set Programme. In the rather different context of what might be called the 'Computational Universe Programme' -- one which associates the complexity of physical phenomena to the emergent features of models such as cellular automata -- a choice problem arises with respect to the variety of formal systems that, in virtue of their computational universality (Turing-completeness), qualify as equally good candidates for a computational, unified theory of physics. This paper proposes Causal Sets as the only objects of physical significance and relevance to be considered under the 'computational universe' perspective, and as the appropriate abstraction for shielding the unessential details of the many different computationally universal candidate models. At the same time, we propose a fully deterministic, radical alternative to the probabilistic techniques currently considered in the Causal Set Programme for growing discrete spacetimes. We investigate a number of computation models by grouping them into two broad classes, based on the support on which they operate; in one case this is linear, like a tape or a string of symbols; in the other, it is a two-dimensional grid or a planar graph. For each model we identify the causality relation among computation events, implement it, and conduct a possibly exhaustive exploration of the associated causal set space, while examining quantitative and qualitative features such as dimensionality, curvature, planarity, emergence of pseudo-randomness, causal set substructures and particles.Source: ISTI Technical reports, 2010
See at:
ISTI Repository | CNR ExploRA