|The Mathematics of Models of Reference - 2D||The Mathematics of Models of Reference - 3D||
Go to the 2D applet
Go to the 3D gallery
|TUTORIAL||back to top|
I. What is a cellular automaton?
II. Why do we study CA?
III. Four lessons from CA
IV. iLabs CA: an introduction to the approach
IV.I. What if the "Teory of Everything" was a CA?
IV.IV. States and rules
IV.V. To think is to be: is this the solution?
V. Learn more
|I. What is a cellular automaton?||back to index|
The theory of cellular automata has its roots in the works of prominent logicians, mathematicians, physicists, computer scientists, such as Alan Turing, John von Neumann, Stanislaw Ulam, John Conway, Stephen Wolfram and Konrad Zuse. Cellular automata (CA) are mathematical representations of complex systems. A complex system is a dynamic system - that is, something changing its state over time and reacting to the environment - whose properties are determined by countless feedbacks and interactions between its parts: a cell, the human body, the U.S. economy are all good examples of complex systems whose behavior is often hard to predict. A distinctive sign of CA is their discrete nature, both in space and in time: almost any CA, in fact, has the following five features:
* A discrete lattice of cells (or atoms); the lattice can be 1, 2, 3 or n-dimensional. The cells are the basic, fundamental bricks of the CA
* Homogeneity: each cell is identical to any other cell in the lattice
* Discrete states: each cell can be in one of finitely many possible discrete states
* Local interactions: each cell interact only with a finite number of cells, its neighbourhood
* Deterministic dynamics: at each instant in time, each cell updates its state with a transition function. The state of a cell at a time t only depends on the states of the cell's neighbourhood at time t - 1.
|II. Why do we study CA?||back to index|
In the wonderful book Cellular Automata: A Discrete Universe, Andrew Ilachinski lists four basic reasons to study CA, in descending order of theoretical interest:
* CA are powerful computational systems
* CA are discrete simulators of dynamical systems
* CA are (a kind of) toy-universe to study the notion of complexity and pattern formation
* CA are models of the fundamental layer of physical reality
With these ingredients, CA can be used to model an impressive variety of phenomena: from gas in a closed space to eletronic circuits, from neural networks to cristal formation, from animal evolution to war strategies.
CA are thus an important element in the new theory of complexity, a multidisciplinary research program pursued in institutions such as the The Santa Fe Institute. The philosophical idea behind all this is that complexity is an emerging phenomena, the results of countless micro-interactions following simple, local rules. On the macro-scale, patterns and events happening in a CA have no immediate or obvious relation to the simple interactions at the micro-scale. The most complex system we know of, of course, is the human brain.
|III. Four lessons from CA||back to index|
To better understand the world of CA we can first consider a classic from the literature: “The game of life”, created by the American mathematician John H. Conway and popularized by Martin Gardner in Scientific American back in the Seventies.
Apart from specific applications in scientific modelling, CA are an incredible toy-universe to test our naive theory of the deep structure of reality and some fundamental concepts of common sense: in particular, several intuitions on objects, movement and complexity are greatly challenged by the study of this systems:
* Lesson 1 → Simple rules can generate incredible complex behavior.
* Lesson 2 → Istantaneous objects can generate "persistent" objects: even if, strictly speaking, a CA is made of istantaneous changes (nothing lasts more than one istant), an observer may receive the illusion that complex patterns move in the universe..
* Lesson 3 → A discrete movement may well approximate a continuous one: patterns moving in Life may seem just as fluid as motions we observe in everyday reality: this suggests that the supposed continuity of our space-time may indeed be an illusion generated by discrete underlying changes.
* Lesson 4 → Several "interpretations" of reality are possible and equally legitimate: even if the Life world is made of black and white squares, we can describe what's going on with different high-level languages. By the same reasoning, we should not forget that also our world - described by high-level names and predicates - may indeed just be composed by simple squares and states.
|IV. iLabs CA: an introduction to the approach||back to index|
We believe that CA are much more than "just" useful models and abstract representations of real phenomena: as a tentative, working hypothesis we are asking ourselves: why reality itself couldn't be a big CA? Of course, this means we are betting on a completely discrete universe, with minimal space-time units and local interactions between elementary cells.
The very idea of discreteness is at the heart of recent developments and extensions of quantum theory: altough nobody knows how the fundamental physical reality truly works, some outstanding scholars have put forward similar considerations in favour of a discrete view of the universe. In this perspective, the (in)famous Theory of Everything - the theory unifying the behavior of any object and event - would be "just" the specification of the structure and the rule governing a CA.
And if our universe is a CA, anything can be decomposed in many elementary cells, whose evolution in time is strictly determined by simple, deterministic rules. Exactly as it happens within Life, the complexity of our world is the (somewhat unexpected) consequence of four elements: space, time, states, rules.
If the space is totally occupied by elementary cells, it is reasonable to assume that cells have a regular shape. Given a three-dimensional space-time there are just three polyhedra that can fill it completely: tetrahedron, cube and rhombic dodecahedron (in two dimensions you have triangle, square and hexagon).
After many preliminary experiments, we chose the hexagon in 2D and the rhombic dodecahedron in 3D: peculiar as they may seem, these two shapes have many advantages over the orthodox square (and cube). For one thing, the distance between cells approximate the radius of a circle/sphere; on the other hand, even if a perfect circle/sphere cannot exist in such a universe, good approximations can be easily generated (see also the Contents section).
Time is composed by discrete units, instants. As we have seen with Conway's Game of Life, a continuous reality may well be an illusion generated by discrete objects moving at a suitable frequency. In general, the idea that time and space are discrete is compatible with the concept of a maximum possible speed - according to Einstein's relativity, the speed of light.
If the universe is a CA, any movement, any change is really just an illusion: what we describe as a "body moving there" is actually the changing in states occurring at many neighbouring cells in several instants of time.
To discover what are the states and rules governing the evolution of the universe is of course a tricky task. Obviously, nobody now can "see" what the fundamental cells are doing, so what we can do is just build reasonable hypothesis and test them against the best data we have: if the world is a CA, we should expect that a given set of states and rules generates macro-behaviors compatible with what we already know. While this is not a real recipe to find the "true" set, it may help the research program to quickly dismiss wrong choices.
If we trust the old simplex sigillum veri motto, the number of states would be not just finite, but also small; by the same reasoning, the rule at the heart of the CA would be very simple and computationally inexpensive: with these guiding principles in mind we are developing our model.
This was one of the most famous Parmenides' statements: it was more than 2500 year ago but, in some sense... iLabs agree with that! Our model is designed explicitely on the assumption of a strong isomorphism between software (thoughts, information, mind) and hardware (reality, physics, body).
Describing the “physical properties" of the world and explaining the “distribution of informational features” are two ways to do one thing: any change in the informational reality is matched by a corresponding change in the physical world - and vice versa. Let's think about something very familiar, our PC: a software instruction (a mouse click, for example) can modify the hard-disk of the PC (the hardware); on the other hand, a modification in the hardware (even unintended ones!) may drastically change the behavior of our software.
Another familiar - although less "standard" - example is the human body. A thought can modify the appeareance and the behavior of the body - the heart beats faster just because you think about your partner! - as well as changes in hardware (for example, a disease) would result in great modification in our cognitive attitudes and abilities.
|V. Learn more||back to index|
The basic text on the subject is of course:
Berto F., Rossi G., Tagliabue J., The Mathematics of Models of Reference, College Publications, 2010 >>
We also list here a collection of books and articles on CA for the interested reader:
Just to start
Advanced introductory texts
Hopcroft J. E. and Ullman J. D., Introduction to Automata Theory, Languages, and Computation, Reading, MA: Addison Wesley, 1979 >>
Ilachinski A., Cellular Automata: A Discrete Universe, Singapore: World Scientific, 2001 >>
Preston, K. Jr. and Duff, M. J. B., Modern Cellular Automata: Theory and Applications, New York: Plenum, 1985 >>
Schiff. J.L., Cellular Automata: A Discrete View of the World, New York: Wiley Interscience, 2008 >>
Crutchfield J.P. and Mitchell M., The Evolution of Emergent Computation, SFI Technical Report 94-03-012
Gardner M., The Game of Life, Parts I-III, Capp. 20-22 in Wheels, Life, and other Mathematical Amusements. New York: W. H. Freeman, 1983 >>
Toffoli T., and Margolus N., Cellular Automata Machines: A New Environment for Modeling, Cambridge, MA: MIT Press, 1987 >>
Von Neumann J., The Theory of Self-reproducing Automata, Urbana, IL: Univ. of Illinois Press, 1966 >>
Wolfram S., Cellular Automata and Complexity: Collected Papers, Reading, MA: Addison-Wesley, 1994 >>
Wolfram S., A New Kind of Science, Champaign, IL: Wolfram Media, 2002 >>
Bennett C.H., Logical Reversibility of Computation, IBM Jour. Res. Dev. 6, 525-32, 1973
Bennett C.H., Thermodinamically Reversible Computation, Phy. Rev. Lett. 53, 1202, 1984
Fredkin E. e Toffoli T., Conservative Logic, Int. Jour. of Theo. Phy. 21, 219, 1982
Margolus N., Physics-Like Models of Computation, Physica 10D, 81-95, 1984
Margolus N., Physics and Computation, PhD thesis, Tech. Rep. MIT Lab. For Comp. Sci., March 1988
Toffoli T., Computation and Construction Universality of Reversible Cellular Automata, Jour. Comp. Sys. Sci. 15, 213, 1977
Toffoli T. e Margolus N., Invertible Cellular Automata, Physica D45, 229-53, 1990
|APPLET 2D||back to top|
I. CA features
I.III. Boolean operators
II.I. The general framework
II.III. Download the offline version
III. Try to...
III.I. Strong reversibility
III.II. Pattern formation
|I. CA features||back to index|
The topology of our universe - in its 2D representation - is based on an hexagonal cell (see also the introductory section in Contents). From a logical point of view, a cell's behavior can be described by a sequence of < perception - thought - action > - that is, the most elementary Model of Reference. In particular, the cell first percieves the bits coming from its neighbourhood; then the cell thinks what to do and finally act, mapping in a suitable way the incoming bits to its new interal state. Ad each update, the cell uses 6 bits to memorize what's happening in the neighbourhood and other 6 bits to "expose" the result of the MoR: since the universe never lose information, the number of bits before and after each update is always the same (this is a necessary, but not sufficient condition to have a CA that is strongly reversible).
The rule - our "super-rule" - defining the behavior of the system is the following:
that is, the sum modulo 2 of the values (1 or 0) in the sextuple of incoming bits. Id is akin to an identity operator, i.e. an operator mapping each sextuple to itself:
Perm is akin to a permutation operator, i.e. an operator switching the elements of a sextuple:
The super-rule allows the perfect representability of boolean operators; moreover, this universe is strongly reversible (something you can easily verify with the interactive applet). But what does it mean exactly reversible? In the CA literature, most rules are not reversible: any function - and so any rule - is said to be not reversible when different input may generate the same output. The rule used by Life, for example, is not reversible, the standard boolean operators are not reversible: universes that are not reversible do not conserve the information in the system, so that it is not possible, by looking at a CA at t + 1 to know its state at the previous instant t.
The super-rule is not just reversible, but strongly reversible, since you can retrieve the input from the output by applying the same rule again. In this case we have that also the "Big Bang" of the universe (i.e. the initial conditions) can be discovered by simply applying "backwards" the rule over and over again.
Patterns and sequences of active and inactive bits may be used to represent a variety of informational process. In our universe, each cell is a universal
logic gate, that can replicate a set of operators that is functionally complete, so that any boolean operation can be computed within the model.
Let's consider an hexagonal cell, where three sides are considered "input" sides and the other three "output" side: this cell has input bits from directions x, y and z (dark grey) and produce output bits in the three opposite sides (grey):
Since boolean operators are not reversible (AND has two input bits and one output bits), some bits will not be considered by the cell simulating the operator. As it turns out, NOT, AND, FAN-OUT and other basic operators can be easily implemented in this universe.
Let's clarify this point with AND and NOT, also illustrated in the video below. If the input z is a “control line” - that is "active" just in case z = 1, the bits arriving from directions x and y will end up producing as output the logical operation x AND y: x AND y = 1 if and only if the input bit x = 1 and the input bit y = 1, 0 otherwise. The NOT operator can be implemented using the same strategy, with z = 1 and y = 0. This time the output of z is the negation of the input of x.
|II. Implementation||back to index|
The 2D CA has been developed using the open platform NetLogo, a free software created by Uri Wilensky to explicitely design agent-based models.
NetLogo is a de facto standard in higher education for scientific modelling of complex systems: by using this solution, we are
ready to share the code and our findings with a large community of existing users; morever, NetLogo is Java based, so that interactive applet for web browser
can be easily created and distributed. Unfortunately, NetLogo is now only partially compiled, slowing the down complex parallel computations.
The code has been written aiming at an almost perfect conceptual clarity: anyone that read the book or some of our articles should be able to go through the code and understand in a few minutes the key parts. A part from setup, import/export data, movies and related issues, the heart of the code is the [go] function, that is in turn based on the [super-regola] function.
[super-regola] has 2 main blocks, allowing the universe to go forward and backward to verify the perfect reversibility: the moment of perception, thought and action are clearly marked in the code.
The offline version of the CA allows the user to save (and load) the state of the universe at a given time, thus enabling the sharing of interesting findings in the research community. Finally, the user may also export a .mov movie of the model. The code (in .nlogo format) is open source and the latest version can be downloaded here. Any comment and suggestion can be sent to our devoted e-mail address.
To use the applet directly within the browser - Mozilla Firefox or Microsoft Explorer - is necessary to have the Java Runtime Environment (Java 6 or higher) installed: Java is a free technology allowing interactive experiences in website and most of the users have already installed some version of it. To verify the Java version installed go to the test page; if the JRE is missing, it can installed in a few minutes downloading the setup file from the same site. Java should be allowed to work by your browser so check your browser options to be sure the JRE is enabled (just follow these instructions).
|III. Try to...||back to index|
...create random initial conditions and let the universe evolve for some instants; then, use the reverse_time-flow option and let evolve the universe again. No matter how many states, objects, patterns there are: the universe will always come back to the "Big Bang"!
...explore the simulations already included in the applet (use the options in the setup menu) or to draw new states on an empty universe and see if you get interesting patterns. Please contact us if you discover new configurations to be included in the next release of our CA.
|3D GALLERY||back to top|