Automatic

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 2⁸ = 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):

1. Trivial: regardless of the initial state, the CA always settles into the same (static or periodic) final state.
2. 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.
3. Chaotic: the evolution of states is apparently random and never settles down to a static or periodic state, though local self-similarities are common.
4. 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.

Wolfram theorised that class 4 CAs are essentially programmable. This is unlikely to be generally provable without circularity (ie, by redefining class 4 to be exactly those CAs that are programmable); nevertheless, one of the class 4 rules (rule 110) has indeed been proved Turing-equivalent, although the initial conditions required for meaningful computation are impractical.
Posted by matt at January 10, 2007 09:12 PM