Essentially, a cellular automaton (CA) is a computing machine that consists of an array of identically programmed "cells" which interact with one another. Typically, the arrays are arranged in a two-dimensional grid or a three-dimensional solid, but honeycomb arrangements are also common. Cellular automata are remarkable in that they are surprisingly simple in definition, yet capable of simulating very complex behaviour normally associated only with living things (reproduction, forming groups, etc.).

The formalism for cellular automata was conceived by John von Neumann in the late 1940s, inspired by the pattern games invented at Los Alamos by mathematician Stanislaw Ulam. Von Neumann was largely successful in describing a self-reproducing cellular automaton, but his machine was huge and took over 100 pages to outline. So in the late 1960s, mathematician John Conway was motivated to extend von Neumann's work by refining the description of the cellular automaton to the simplest one that could support universal computation. Conway's automaton had only two states, on and off, and had very simple but lifelike rules for determining what the next states should be (see The Game of Life).

Perhaps the best way to intuitively demonstrate the modelling power of cellular automata is through producer-consumer dynamics. The following CA uses a set of simple rules to simulate the classic plant-herbivore-carnivore ecosystem:

• For every time step:
  • For every empty cell, e:
    
    
    • If e has 3 or more neighbours that are plants, then e will become a plant at the next time step (assuming it isn't trampled by a herbivore or carnivore).
  
  
  
  • For every herbivore, h (in random order):
    
    
    • Decrease energy reserves of h by a fixed amount.
    • If h has no more energy, then h dies and becomes an empty space.
    • Else, if there is a plant next to h, then h moves on top of the plant, eats it, and gains the plant's energy.
      • If h has sufficient energy reserves, then it will spawn a baby herbivore on the space that it just exited.
    • Else, h will move into a randomly selected empty space, if one exists, that is next to h's current location.
  
  
  
  • For every carnivore, c (in random order):
    
    
    • Decrease energy reserves of c by a fixed amount.
    • If c has no more energy, then c dies and becomes an empty space.
    • Else, if there is a herbivore next to c, then c moves on top of the herbivore, eats it, and gains the herbivore's energy.
      • If c has sufficient energy reserves, then it will spawn a baby carnivore on the space that it just exited.
    • Else, c will move into a randomly selected empty space that is next to c's current location. If there are no empty spaces, then c will move through plants.

If you were to plot the population levels of the three species, you would obtain a graph that looks roughly like three overlapping sinusoids, with the plant wave first, the herbivore wave just ahead of the plant wave, and the carnivore wave just ahead of the herbvore wave¹. This makes sense since as the plant population increases, the herbivore population will graze on it and increase, decreasing the plant population but increasing the carnivore population which, in turn, will decrease the herbivore population, and eventually will decrease the number of carnivores, and on and on²... Congratulations! You're the proud owner of an attractor!

For some really neat CA Java applets to play with, visit the following sites:

http://www.mirwoj.opus.chelm.pl/ca/
http://www.ibiblio.org/lifepatterns/ (thanks jrn!)

---

¹I'm not sure my ASCII art skills are up to the challenge--for you EEs out there, think of 3-phase AC! ;)
²Well, the concept makes sense at least, but I don't think I can say the same for this sentence...

REFERENCES:

Flake, Gary William. The Computational Beauty of Nature: Computer Explorations of Fractals, Chaos, Complex Systems, and Adaptation. Cambridge: MIT Press, 1998.
http://www.brunel.ac.uk:8080/depts/AI/alife/al-ca.htm

A cellular automaton is really nothing more than an array or a transitive graph of identical finite state machines (aka DFAs), feeding on themselves! (Or, if you want to add randomness, you also add randomness to your machines.)

The possible states of each cell are the states of its finite state machine. At every time step, each cell receives as input the states of its neighbours (there are a finite number of neighbours, and each can be in one of a finite number of states, so this input comes from a finite alphabet). The combination of the cell's current state and its input (a finite amount of information) yields the cell's state in the next time step.

For instance, Conway's Game of Life consists of a 2D array of cells. Each cell has 2 possible states (dead or alive). There are 8 neighbours for each cell, so the input is from an alphabet of size 2⁸=256, giving the states of all cells. Of course the transition function is particularly simple: A dead cell turns alive if it has exactly 3 live neighbours, i.e. it receives one of the 56 possible inputs with exactly 3 1's. A live cell stays alive if it has exactly 2 or 3 live neighbours, i.e. it receives either one of these 56 inputs or one of the 28 inputs with exactly 2 1's.

Note that a Turing machine can easily be modeled in this fashion, essentially by arraying machines along the number line Z. Each machine either represents a tape cell or a tape cell occupied by the Turing machine's head. The rules of the Turing machine are easily adapted to the rules for the 1D cellular automaton. So it's not too surprising that Conway found a cellular automaton (Life) capable of computing any computable function; the surprise is that it's such a simple automaton!