Cellular Automata

The study of cellular automata is an exciting new area of mathematical and scientific research. In

fact, in “A New Kind of Science”, mathematician Stephen Wolfram argues that the study of complexity arising from considering cellular automata is the starting point of a new scientific revolution. Although I wouldn’t go this far, I do find them quite fascinating.

A cellular automaton (CA) is a set of cells with states which evolve according to a set of deterministic rules. The simplest cellular automata have cells with just two possible states, off and on, and evolve according to very simple rules, usually involving just neighboring cells. Wolfram studied all 256 one-dimensional two-state cellular automata which evolve according to nearest neighbor rules. He then divided these automata into four classes according to the type of behavior they exhibit. Class 1 cellular automata eventually evolve to a state in which all cells are either off or on. Class 2 cellular automata evolve into a predictable pattern, i.e. alternating off and on cells. Class 3 cellular automata exhibit what appears to be random behavior. Finally, Class 4 cellular automata, which are the most interesting, evolve into states exhibiting nonrandom but nevertheless unpredictable structure. Wolfram believes that Class 4 cellular automata are akin to Turing machines and as such may be capable of universal computation.

The most well-known CA is Conway’s Game of Life. This is a two-dimensional two-state CA played on an infinite square grid. The rules are very simple. An on cell with two or three of its eight nearest neighbors on stays on in the following generation, otherwise it turns off, and an off cell with three nearest neighbors on turns on in the next generation, otherwise it stays off. These simple rules give rise to surprisingly complex structures, including still lifes (patterns that don’t change), oscillators (patterns which repeat), spaceships (patterns which move), and a variety of complex patterns which experience regular unlimited growth. In 1982, Conway showed that the Game of Life supports Turing machines, and the first one was constructed in 2002.