256 Universes in One Dimension
An elementary cellular automaton is perhaps the simplest possible computer: a row of cells, each either black or white, updating simultaneously based on a rule that considers each cell and its two neighbors. With 8 possible neighborhood configurations and 2 possible outputs each, there are exactly 256 possible rules — 256 tiny universes, each with its own physics. Stephen Wolfram spent decades exploring all of them.
Wolfram's Four Classes
Despite the simplicity of the rules, the behaviors they produce span an enormous range. Wolfram classified them into four classes: Class 1 rules kill everything (like Rule 0 — all cells die). Class 2 rules produce periodic patterns (like Rule 4 — stable triangles). Class 3 rules produce apparent randomness (like Rule 30 — used by Mathematica for random number generation). And Class 4 rules produce complex, structured patterns with long-lived interacting objects.
The Edge of Chaos
Chris Langton showed that these four classes correspond to a phase transition parameterized by lambda, the fraction of active rule outputs. At low lambda, rules are too simple (Class 1-2). At high lambda, rules are too chaotic (Class 3). At the critical value — the edge of chaos — complex computation emerges (Class 4). This is where information storage and transmission are balanced, enabling the rich dynamics needed for computation.
Rule 110 and Universal Computation
The crown jewel of elementary cellular automata is Rule 110, proven Turing complete by Matthew Cook in 2004. This means that given enough cells and enough time, Rule 110 can compute anything a modern computer can. From a simple 3-cell rule emerges universal computation — perhaps the most profound demonstration that complexity need not require complex rules.