Cellular Automata
Cellular Automata are a class of models that are discrete in
space, time and state. They are typically quite simple, allowing only
local interactions according to uniform rules, but can often usefully
approximate systems whose representation in continuous mathematics, even
given many simplifying assumptions, is intractable; in particular
systems of differential and integral equations defining complex
interdependencies between many variables. In essence, they exchange the
mathematical complexity for lack of resolution and often high levels of
parallelism.
Although CAs can themselves be arbitrarily complicated, it is more usual
to break down the problem domain into almost trivial units; especially
so when the problem domain is cellular automata themselves, which turn
out to be very behaviourally interesting in their own right.
The most commonly encountered CAs consist of a rectangular array of
cells, each of which can be in one of a finite number of states. The
state of a cell at each time step is calculated from the states of some
number of cells (the cell's neighbourhood) in the previous time
step, according to some fixed rules. All cells in the CA are usually
governed by the same rules, and their neighbourhoods are usually defined
consistently (with appropriate conditions at the boundaries). Cells are
processed in parallel.
While the specification of a cell's neighbourhood is potentially
arbitrary, for convenience and intuitiveness we normally define it to be
the cells directly adjacent in the array -- there is thus an
equivalence between the neighbourhood and the dimensionality of
the CA.
In a standard CA, every cell is an automaton, processed at each step
regardless of its state. There are variant forms, such as Lattice
Gases and Effector Automata, in which the cell array provides
the geography within which some smaller number of automata move
around. Intuitively it seems likely that these different forms are
simply optimizations, but I don't know if this equivalence has actually
been proved (or indeed is provable or true).
The most famous cellular automaton is John Conway's Game of Life,
a two-dimensional, two-state CA with very simple rules: a dead cell with
3 neighbours comes to life, a live cell with 2 or 3 neighbours remains
alive, all other cells die or remain dead. The neighbourhood includes
diagonally adjacent cells. Many interesting patterns are possible
with this CA, and in fact it has been demonstrated to be Turing
equivalent, which is to say capable of universal computation: given
a sufficiently large array of cells and inhuman levels of
bloody-mindedness, you could set the game up to perform any calculation
that can be done by the computer on which you're reading this.
The applet below demonstrates a set of even simpler one-dimensional,
two-state CAs. A cell's neighbourhood includes only one cell on each
side (this implementation uses periodic boundary conditions,
which is to say the space is circular: the rightmost cell is considered
to be the left neighbour of the leftmost; multiple generations are
displayed, with time increasing downwards). With such a configuration
there are exactly eight possible states for the cell and its
neighbourhood in any generation, and hence exactly
28 = 256 possible possible rule sets
mapping those states deterministically to a cell state for the next
generation. Each set can be uniquely identified by a number from 0 to
255, in a scheme devised by Stephen Wolfram.
This Wolfram number is shown by the applet, but rules are actually
specified using the state controls on the right hand side: click to
toggle the next-generation state for a cell given the neighbourhood
state shown at the top of the control. Once you've defined your rules,
restart the CA to see it in action. Explore them all!
A cellular automaton's behaviour depends on its initial state as well as
its rules; the applet allows you to start from either a random start
state or a single "seed" cell in the middle of the row. (Note that the
applet doesn't currently display the start state, beginning instead with
the first filial generation; this may be fixed if I get around to it.)
Although some rules produce immediately obvious results (eg, rule 0 or
rule 255), for others you may need to look at many different runs to get
a sense of how the rule tends to behave.
Wolfram (again) -- a cellular automaton obsessive, who wrote and
self-published a gigantic tome arguing that CAs constitute a
revolutionary scientific paradigm capable of explaining pretty much
everything -- identified four different classes of CA behaviour, all of
which can be found among the 256 rules in the applet (pace the
finite number of cells):
- Trivial: regardless of the initial state, the CA always settles into the same (static or periodic) final state.
- Simple: different initial states lead to different terminal states, but the system always settles into a static or periodic final state within a finite number of steps.
- Chaotic: the evolution of states is apparently random and never settles down to a static or periodic state, though local self-similarities are common.
- Complex: the behaviour varies dramatically according to the initial state and is qualitatively unpredictable -- you have to actually run the CA from a state to find out what it will do.