Cellular automata and the Game of Life

A cellular automaton is a grid of cells, each in one of a few states, all updated together by a rule that looks only at a cell and its neighbours. That is the entire idea. It is also one of the clearest demonstrations ever built that simple local rules can produce behaviour nobody wrote down.

Background concept

Conway's Game of Life

The best known example was devised by John Conway in 1970. Cells are alive or dead on a square grid, and every cell updates at once according to four rules:

Nothing in those four lines mentions a shape. Yet the Game of Life contains stable blocks, oscillators that repeat on a cycle, gliders that travel across the grid, guns that emit a stream of gliders, and arrangements that perform arbitrary computation. The Game of Life is Turing complete: anything a computer can compute, a sufficiently large starting pattern can compute too.

Why this matters beyond the toy

The Game of Life settled an argument by demonstration. Before it, the claim that unlimited complexity could follow from a handful of local rules was mostly an intuition. Afterwards it was something you could run.

Elementary automata and Rule 110

Stephen Wolfram catalogued the simplest possible case: a one-dimensional line of cells, two states, each cell updated from itself and its two neighbours. There are exactly 256 such rules. Most produce something dull, either dying out or repeating forever. A few do not. Rule 30 produces a stream that passes statistical randomness tests despite being fully deterministic. Rule 110 was proved Turing complete, which means universal computation is available in about as small a system as can be described.

The link to artificial life

Cellular automata are the ancestor of most of the field. John von Neumann used one in the 1940s to design a self-reproducing machine, and the question he was answering, what a system needs in order to build a copy of itself without the copy degrading, is still central. His answer, that it needs a description of itself which it both copies and interprets, turned out to describe how DNA is used, years before that was understood biologically.

Later work, particularly Langton's, asked which rules produce interesting behaviour at all, and found that the productive ones sit in a narrow band between rules that freeze and rules that dissolve into noise. See artificial life for how the field grew out of this.

What Emergent Life shares, and what it does not

Emergent Life is not a cellular automaton, but it inherits the discipline. The world is a grid with local rules, the environment updates on a fixed tick, and no rule anywhere names a shape, a strategy or an outcome. Terrain material is conserved and moved locally, which is described in reshaping the world.

The difference is that the cells are not the interesting part. Organisms here are separate entities with their own inherited state and their own neural controller, so the system is closer to an agent-based model that sits on a grid than to an automaton whose rule is the whole story. That choice buys inheritance, mutation and selection, which a plain automaton has to encode by hand, at the cost of a much larger rule set to defend.

References and further reading

Primary sources for the claims on this page. Where this project's own results are referred to, they link to the page carrying the evidence instead.

  1. von Neumann, J. (1966). Theory of Self-Reproducing Automata (A. W. Burks, Ed.). University of Illinois Press.
  2. Gardner, M. (1970). Mathematical Games: The fantastic combinations of John Conway's new solitaire game 'life'. Scientific American, 223(4), 120-123.
  3. Langton, C. G. (1990). Computation at the edge of chaos: Phase transitions and emergent computation. Physica D, 42(1-3), 12-37. doi:10.1016/0167-2789(90)90064-V
  4. Cook, M. (2004). Universality in Elementary Cellular Automata. Complex Systems, 15(1), 1-40.

Keep reading

Watch the live world