Introduction to Cellular automata

    There is a wealth of literature about cellular automata, as well as many Internet resources (you'll find some of them in the links section). The aim is here much more limited. This site being devoted to laymen, I will content myself with answering both main questions any person discovering cellular automata often ask, generally after a period of intense perplexity :

1. What might this be ?
2. What could be the applications for such a thing ?

    The answer to these questions is unfortunately far from being simple. cellular automata are abstract constructions with quite complex properties not very accessible.

   A-  History

    The history of cellular automata dates back to the forties with Stanislas Ulam. This mathematician was interested in the evolution of graphic constructions generated by simple rules. The base of his construction was a two-dimensional space divided into "cells", a sort of grid. Each of these cells could have two states : ON or OFF. Starting from a given pattern, the following generation was determined according to neighbourhood rules. For example, if a cell was in contact with two "ON" cells, it would switch on too ; otherwise it would switch off. Ulam, who used one of the first computers, quickly noticed that this mechanism permitted to generate complex and graceful figures and that these figures could, in some cases, self-reproduce. Extremely simple rules permitted to build very complex patterns. On that basis, the following question was asked : can these recursive mechanisms (i.e. in that case depending on their own previous state) explain the complexity of the real ? Is this complexity only apparent, the fundamental rules being themselves simple¹ ?

    As a sideline, John von Neumann, relying on A. Turing's works, interested himself on the theory of self-reproductive automata and worked on the conception of a self-reproductive machine, the "kinematon". Such a machine was supposed to be able to reproduce any machine described in its programs, including a copy of itself². The most famous of his machines is the monolith of the series "2001 Space Odyssey". To change Jupiter into a star, a first monolith self-reproduces, as well as its descendants, the population so increases exponentially to quickly reach the size necessary to realize such a gigantic task.

    Ulam suggested von Neumann to use what he named "cellular spaces" to build his self-reproductive machine. He could so liberate himself from real physical constraints to work in an extremely simplified universe that was nevertheless able to generate a high complexity. The use of this formal universe led him to notice : "By axiomatizing [self-reproductive automata with cellular automata], one has thrown half of the problem out the window, and it may be the more important half. One has resigned oneself not to explain how these parts are made up of real things, specifically, how these parts are made up of actual elementary particles, or even of higher chemical molecules. [...] The question we hope to answer now [...] is : what are the basic principles which underlie the organization of these elementary parts in living organisms ? My discussion will be limited to that point of vue."³. On this base, he designed an about 200.000 29 states cells , containing a universal replicator, a description of itself and a Turing machine for supervision⁴.

    Cellular automata left laboratories in 1970 with the now famous Game of Life of John Horton Conway.

    B- The Game of Life

    Originally, the Game of Life is presented as a mathematical game. Its description will allow us to materialize and better understand what cellular automata are.

    Like Ulam's cellular spaces, the game of life is based a grid constituted of cells, for example :

Example of a starting pattern

    The universe is here limited to a rectangle of 5 by 3. To make the explanation easier, we numbered the cells from 0 to 4 horizontally and from 0 to 2 vertically. Light cells are active ones.

    In the game of life, any adjoining cell is considered as neighbour, including diagonals.

Determination of neighbourhood

    The graphic above shows the neighbourhood of cell 12. In this case, two cells are active out of the 8 neighbours.

    The rules of the game of life are quite simple :

1. One inactive cell surrounded by three active cells becomes active ("it's born") ;
2. One active cell surrounded by 2 or 3 active cells remains active ;
3. In any other case, the cell "dies" or remains inactive.
   

    We can interpret these rules by considering that a birth supposes a certain gathering of population, (3 in this case), that the cells cannot survive to a too wide isolation (less than two neighbours) and that a too strong concentration will kill them (more than 3 neighbours).

    Cellular automata work in a discrete manner. That is to say time goes step by step. This means that in our case, for the g generation, each cell examines its environment and determines its future state. When all the cells have fulfil this computation, the transitions occur. We so simulate a simultaneous treatment.

    Let us illustrate this mechanism starting from the previous pattern :

First generation

    In the previous pattern, the number of active neighbours is noted for each cell :

1. The cells 00, 04, 10, 14, 20 and 24 have got one active neighbour and then remain inactive.
2. The cells 01, 03, 21 and 23 have got two active neighbours, and then do not change.
3. The two inactive remaining cells (02 and 22) have got three active neighbours, the rule 1 is applied : they are born.
4. The cells 11 and 13 have only one active neighbour : they die.
5. Finally the cell 12 having two active neighbours, it remains alive.

    For the next generation, only the cells 02,12 and 22 are then active.

Second generation

    We show there the three fundamental properties of cellular automata⁵ :

1. Parallelism : A system is said to be parallel when its constituents evolve simultaneously and independently. In that case cells update are performed independently of each other.
2. Locality : The new state of a cell only depends on its actual state and on the neighbourhood.
3. Homogeneity : The laws are universal, that's to say common to the whole space of cellular automata.

    C- Other Cellular Automata

    The game of life is only one type of cellular automata among an infinity. It is indeed possible to play on the whole rules that govern the universe of cellular automata.

    The most obvious parameter is the number of dimensions. Indeed, nothing obliges to consider two dimensions environments. The theoretical analysis of cellular automata was mainly made out of one dimension automata. By reducing the number of dimensions, one limits the combinatory explosion, hence the number of possible automata. If we consider the simple case of a three cells neighbourhood, i.e. the concerned cell and its right and left neighbours, in a one dimension and two states automaton, there are only 2 power 2³=256 possible rules. With one dimension automata (i.e. one line) we use the second dimension to represent time. For each generation, a new line is added below the former one, we can so visualize the dynamic of this type of automata.

Example of a 1 dimension automaton (Pascal's triangle)

    It is obviously possible to create three (or more) dimensions automata.

    It is also possible to modify the determination of neighbourhood. If we consider two dimensions automata, the most common neighbourhoods are⁶ :

1. Von Neumann : only North/South/East/West neighbours are considered ;
2. Moore : one adds the diagonals. It's the case of the game of life ;
3. Extended Moore : one extends the distance of neighbourhood beyond one ;
4. Margolus : one considers groups of 2x2. It's this type of neighbourhood that is used in the simulation of gas behaviour.
   

    For example, Fredkin's automata, that uses a Moore neighbourhood is based on the parity of neighbourhood. It's a totalistic automaton, that is to say the state of the cells depends on the sum of the states of neighbouring cells. In this case there is reproduction only if there is an odd neighbourhood value. This automata has got the remarkable property to reproduce nine copies of any basic pattern. Fredkin's rule can easily be generalized to more than two dimensions⁷.

Fredkin generation 0

Fredkin generation 8

    It is also possible to modify the number of states. You needn't restrict yourself to both states life/death. Numerous famous automata use more than two states. One of the most famous is Brian's Brains presented by Brian Silverman in 1984. This three states automaton (life, ghost, death) generates a wide diversity of complex gliders within astonishing graphic patterns.

Brian's Brain

    More complex rules can be imagined. It's possible, for example, to build stochastic automata whose transition rules integrate a probability function.

    In a general way, it is possible to build any type of automata by playing on structural and functional rules. The first ones define the spatial structure of the automata network, that is its number of dimensions, the disposition of cells (squares, hexagons,… in a two dimensional automaton) and the type of neighbourhood determination. The second ones will determine the number of states and the transition rules⁸. The choice of these two types of rules permits to build a universe adapted to the demanded aim.

1- Heudin JC, La Vie Artificielle, Hermès, Paris, 1994, p. 35.

2- This causes a big recursion problem. The machine has to contain a self-description, but in order to be complete this description must be described too... etc... To solve this problem, the machine must be able to interpret the description as a program, a set of instructions, and as a component. The description will then be computed to construct the new machine, and then only copied in order to give the new machine a self-description. This mechanism corresponds to the current interpretation of the functioning of DNA discovered after von Neumann's work.

3- Von Neumann J. et Burks A. ed., Theory of Self-Reproduction Automata, University of Illinois Press, 1966, p. 77, in Ostolaza J.L., Bergareche A.M., La vie artificielle, Seuil, Paris, 1997, pp. 37-38. Translated from French.

4- Heudin, Idem, p. 39.

5- Rucker R., Walker J., Introduction to CelLab, http://www.fourmilab.ch/cellab/

6- Shatten A., Cellular Automata, Institute of General Chemistry Vienna University of Technology, Austria, 1997.

7- Rucker R., Walker J., op.cit.

8- Langlois A., Phipps M., Automates cellulaires. Application à la simulation urbaine. Hermès, Paris, 1997. p. 17.