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.

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.

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.

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

Game of Life di John Conway >> wiki - site - NetLogo code
The wiki entry on “Cellular Automato” >>
The MathWorld entry on “Cellular Automaton” >>

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 >>

Classics

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 >>

Reversible CA

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

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.

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).

...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.