Cellular automata
Life is one member of a family of systems that predates it by twenty years and was invented to answer a question about whether machines could reproduce.
What makes an automaton cellular
A cellular automaton needs four things and nothing else:
- a lattice of cells - a line, a grid, a honeycomb, a cube;
- a finite set of states each cell can be in;
- a neighbourhood definition - which cells count as adjacent;
- a transition rule mapping a cell's state and its neighbours' states to its next state.
The rule is applied to every cell at once and identically everywhere. There is no central controller, no global variable, no communication beyond the neighbourhood. Everything a cellular automaton does, it does locally. That constraint is what makes the results interesting: nothing in the rules of Life mentions gliders, and yet gliders exist.
Ulam and von Neumann
In the late 1940s at Los Alamos, Stanisław Ulam was using the lab's early computers to study the growth of crystals with simple lattice models. At the same time John von Neumann was stuck on a question he had set himself: what would a machine need in order to build a copy of itself?
His first attempt involved a robot floating in a lake of spare parts, which was hopeless to reason about rigorously. Ulam suggested he drop the physics entirely and work in a discrete lattice instead. The result, worked out around 1952 and published posthumously in 1966, was the universal constructor: a cellular automaton with 29 states per cell and a Moore neighbourhood, containing a configuration of roughly 200,000 cells that could read a description tape, build the machine it described, copy the tape, and hand it to the offspring.
Before the discovery of DNA's structure
Von Neumann's design separates the description of the machine from the machinery that reads it, and uses the description twice - once as instructions, once as data to be copied verbatim. Watson and Crick published the double helix in 1953. Von Neumann had derived the logical necessity of the arrangement from first principles, without knowing that biology had already implemented it.
Conway's simplification
Von Neumann's automaton was correct and almost unusable - 29 states, a rule table nobody could hold in their head, and a self-replicator too large to simulate on the hardware of the day. The obvious question was how far it could be cut down.
In 1970 Conway's answer was: two states, eight neighbours, four rules. It was not obvious at the time that anything so austere could support universal computation. It took until 1982 for a construction to be published - and the mere existence of the glider gun in 1970 had already shown the door was open.
Wolfram's 256 rules
The simplest interesting cellular automata are one-dimensional: a single row of cells, two states, and a neighbourhood of three (the cell and its two immediate neighbours). There are 2³ = 8 possible neighbourhoods, and a rule assigns an output to each - so there are 2⁸ = 256 possible rules, the whole space small enough to enumerate exhaustively.
Stephen Wolfram did exactly that in the early 1980s, numbering each rule by reading its eight outputs as a binary number. Drawing successive generations as rows down the page turns the automaton's whole history into a single image. Wolfram sorted the results into four classes:
| Class | Behaviour | Example |
|---|---|---|
| I | Settles to a uniform state | Rule 0, Rule 255 |
| II | Settles to stable or periodic structures | Rule 4, Rule 108 |
| III | Chaotic, aperiodic, statistically random | Rule 30, Rule 90 |
| IV | Localised structures that interact in complex ways | Rule 110 |
Conway's Life is a class IV system in two dimensions. Class IV is the interesting one precisely because it is the one that supports computation - it needs stable structures to store information and moving structures to carry it.
Rule 30 and randomness
Rule 30, started from a single live cell, produces a pattern whose left half is regular and whose right half appears completely random. Wolfram was struck enough by this to use its centre column as the random number generator in Mathematica for years. The sequence has passed statistical randomness tests, and yet it is produced by a rule you can state in one line and iterate on paper.
The same pattern occurs in nature: the shell of the sea snail Conus textile carries pigmentation strikingly similar to Rule 30's output, apparently produced by a comparable local activation-inhibition process in the mantle.
Rule 110 is a computer
Wolfram conjectured in the 1980s that Rule 110 - a one-dimensional, two-state, nearest-neighbour automaton - was capable of universal computation. In 2004 Matthew Cook published the proof.
Rule 110 supports a periodic background, several distinct localised structures that travel through it at different speeds, and collision reactions between them that can be arranged to implement a cyclic tag system, which is Turing complete. The implication is startling: the simplest non-trivial class of automaton that exists already contains everything computation can do. Universality is not rare and hard-won. It is nearly unavoidable.
Langton, ants and the edge of chaos
Christopher Langton, who coined the term artificial life in 1986, introduced a parameter λ measuring roughly what fraction of a rule's transitions lead to a non-quiescent state. Sweeping λ from 0 upwards takes a system from frozen order, through a narrow band of complex behaviour, into chaos. The band is the edge of chaos, and it is where computation appears to be possible - a system that is too ordered cannot carry information, and one that is too chaotic cannot preserve it.
Langton also introduced the automaton now known as Langton's Ant: a single agent on a grid that turns right on white, left on black, and flips the square it leaves. For about 10,000 steps it produces apparent chaos, and then - always, from every starting configuration tested - it settles into a repeating 104-step cycle that builds a diagonal "highway" forever. Nobody has proved that it must.
Other automata worth knowing
- WireWorld (Brian Silverman, 1987)
- Four states designed to model electronics. Electron heads become tails, tails become wire, and wire becomes a head only if exactly one or two neighbours are heads. Sufficient to build diodes, gates, and a working computer that computes primes.
- Brian's Brain (Brian Silverman)
- Three states with a mandatory refractory period: every firing cell must spend a generation dying before it can be reused. The result is a world almost entirely composed of moving structures - closer to neural tissue than to Life.
- Lattice gas automata
- HPP and FHP model fluid dynamics with particles hopping between lattice sites and colliding under conservation rules. In the large-scale limit they recover the Navier-Stokes equations - real physics from a cellular automaton.
- Turmites
- Generalised Langton ants with more internal states and more colours. Some build symmetric structures, some spirals, some behave chaotically forever.
- Continuous automata
- SmoothLife and its successor Lenia replace the discrete grid and binary states with continuous fields and smooth kernels. Lenia produces gliding, rotating, self-repairing creatures that look uncomfortably biological.