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 :
The answer to these questions is
unfortunately far from being simple. cellular automata are
abstract constructions with quite complex properties not very
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 simple1 ?
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 itself2.
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."3. 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 supervision4.
Cellular automata left laboratories in
1970 with the now famous Game of Life of John Horton Conway.
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 :
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 :
In the previous pattern, the number of active neighbours is noted for each cell :
For the next generation, only the cells 02,12 and 22 are then active.
We show there the three fundamental properties of cellular automata5 :
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 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
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 are6 :
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
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.
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 rules8.
The choice of these two types of rules permits to build a universe
adapted to the demanded aim.
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.
5- Rucker R., Walker J., Introduction to CelLab, http://www.fourmilab.ch/cellab/
Copyright ©rennard.org. 2000, 2001, 2002.