About Cellular Automata
The applets in the preceding page illustrate various cellular automata rules. Those rules are very simple, but as you can see, the result of often very complex.
CA started in the 1940s with mathematician Stanislas Ulam. He was interested in the evolution of graphic constructions generated by simple rules. The base of his construction was a grid divided into ‘cells’. Each cell could have two states : ON or OFF.
Starting from a given pattern, the next 'generation' of cells could be 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 generated complex and graceful figures and that these figures could, in some cases, self-reproduce. Extremely simple rules allowed very complex patterns.
Cellular automata left laboratories in 1970 with the now famous Game of Life developed by John Horton Conway.
Originally, the Game of Life was presented as a mathematical game. But it gives us a better understanding of 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,the cells have been numbered 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 :
- One inactive cell surrounded by three active cells becomes active (it's born)
- One active cell surrounded by 2 or 3 active cells remains active
- In any other case, the cell ‘dies’ or remains inactive.
The rules then are a birth supposes a certain gathering of population, (three 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 three neighbours).
Cellular automata work in a discrete manner. That means ‘time’ goes step by step. This means that in this case, for each generation, each cell examines its environment and determines its future state. When all the cells have made this computation, transitions occur.
The mechanism can be illustrated starting from the previous pattern :
First generation
In the previous pattern, the number of active neighbours is noted for each cell:
- The cells 00, 04, 10, 14, 20 and 24 have got one active neighbour and then remain inactive.
- The cells 01, 03, 21 and 23 have got two active neighbours, and then do not change.
- The two inactive remaining cells (02 and 22) have got three active neighbours, the rule 1 is applied: they are born.
- The cells 11 and 13 have only one active neighbour: they die.
- 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
There are three fundamental properties of cellular automata:
- Parallelism : A system is said to be parallel when its constituents evolve simultaneously and independently. In that case cell updates are performed independently of each other.
- Locality : The new state of a cell only depends on its actual state and on the neighbourhood.
- Homogeneity : The laws are universal, that's to say common to the whole space of cellular automata.
The game of life is only one type of cellular automata among an infinity. It’s possible to play with the rules that govern the universe of cellular automata.
The most obvious parameter is the number of dimensions. 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 23=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:
- Von Neumann : only North/South/East/West neighbours are considered
- Moore : one adds the diagonals, such as in the game of life
- Extended Moore : one extends the distance of neighbourhood beyond one
- 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.
