Cellular automata

Why can a grid of cells obeying three trivial rules build structures nobody wrote into them?

A grid of squares, each either on or off. Every tick, each square looks at its immediate neighbours and applies one fixed rule. No plan, no memory beyond one step, nothing that sees more than a square away — and out of it come gliders that travel, oscillators that tick, guns that manufacture gliders forever, and eventually machines that compute.

The reflex is to say the structures were "hidden in the rules". But the rule is three clauses long and mentions none of them. So what does it mean to say complexity came from simplicity?

Start with the smallest version, where everything is countable. Take a single row of cells, each on or off, and let each cell's next state depend on itself and its two neighbours. Three cells, so eight possible neighbourhoods, and a rule assigns an output to each: eight binary choices, 2 to the 8, or 256 rules. That is the whole universe of elementary cellular automata, each named by reading its eight outputs as a binary numeral — which is where "Rule 110" and "Rule 90" come from.

Now run one. Rule 90 turns a cell on exactly when its two neighbours differ — the exclusive-or of left and right. Start with a single lit cell in an infinite dark row and what appears is the Sierpinski triangle: nested triangular voids at every scale, unmistakably intricate.

But test the intuition that intricate means complex. In Rule 90 the cell in row n, column k is lit exactly when the binomial coefficient "n choose k" is odd. That is a closed form: you can state the contents of row one billion, column four million without running a step, by inspecting the binary digits of the two numbers. Rule 90 produces an ornate picture and no complexity whatever — a solvable formula in a fractal costume. Most of the folklore here fails to survive that one observation.

So what would count as the real thing? Ask what a system needs in order to compute: signals carrying information from place to place, something stable holding a value, and a way for signals to interact. Conway's Game of Life — two dimensions, eight neighbours, a live cell surviving on two or three live neighbours and a dead cell coming alive on exactly three — has all three. Gliders, five-cell patterns translating one square diagonally every four ticks, are the signals. Still lifes are the storage. Gliders collide in ways that depend on their relative timing, and that is the interaction. Add a glider gun and you have a source of ones. From those pieces people have built logic gates, memory registers and a universal computer inside the grid.

That is the honest content of "complexity from simple rules": not that the pattern looks rich, but that the system can be made to carry out any computation. Rule 110 — one elementary rule on a single line of cells — is universal too, proved by Matthew Cook and published in 2004, which I state from recall.

Now the consequence, which is the part that matters. Once a system is capable of universal computation, questions about its long-run behaviour inherit the undecidability of the halting problem. No general shortcut tells you whether an arbitrary Life pattern eventually dies out; the only reliable way to learn what one does in a million steps is to run a million steps. The structures were not hidden in the rules waiting to be read off, because reading them off is provably impossible in general.

"Cellular automata prove complexity arises from simple rules" is a claim about possibility, not tendency. What is established is that some simple rules support universal computation. Most of the 256 elementary rules do nothing interesting: they blank the row, fill it, or settle into stripes within a few steps. Interesting behaviour is the exception, and the correct statement is that simple rules do not forbid complexity — weaker and far more useful than the claim usually made.

Universality needs an engineered starting condition. Rule 110's computation is not something you see by seeding a random row and watching. The proof constructs an elaborately prepared initial configuration encoding the machine simulated, and a Life computer is likewise built cell by cell by a human. Random soup in Life settles into blinkers and blocks, not a processor. Conflating "capable of universality" with "spontaneously computes" is the commonest error here.

The four-class taxonomy is description, not theorem. Sorting rules into homogeneous, periodic, chaotic and complex is vocabulary popularised by Stephen Wolfram, but the classes have no sharp definition and membership is undecidable. The broader Principle of Computational Equivalence is a conjecture.

What this does not say about physical patterns. The neighbouring walk-throughs on convection cells and patterned ground describe real pattern formation, and the difference is worth stating sharply. Those systems have energy flowing through them and their pattern is selected — an instability picks a wavelength because that scale transports heat or sorts stones best. A cellular automaton has no energy, no dissipation and nothing to select: its pattern is not favoured over alternatives, it is simply computed. So automata demonstrate that locality plus iteration suffices for structure, and explain poorly why any particular physical pattern is the one nature chose.

What would refute the strong reading. If someone claims an automaton's structures are genuinely irreducible, the test is whether a shortcut exists. Rule 90 has one, as do all additive rules, whose behaviour superposes linearly and can be jumped forward directly. Find such a shortcut and the intricacy was decorative.

• The construction of logic gates from glider collisions, and what a Life computer looks like.
• Lattice-gas automata, tuned so their coarse-grained behaviour reproduces fluid flow.

Every term the collection defines is gathered in the glossary.