2026-04-11
Three bits in, one bit out. A cell looks at itself and its two neighbors, and a lookup table decides what it becomes next. There are 256 possible lookup tables — 256 possible rules — and that's the entire space of elementary cellular automata.
Most of these rules are boring. Rule 0 kills everything. Rule 255 fills everything. Rule 204 is the identity — nothing changes. But somewhere in the space between trivial death and trivial stasis, something unexpected happens.
Stephen Wolfram spent the early 1980s systematically running all 256 rules and watching what happened. He found four behavioral classes.
Class I rules converge to a uniform state. Every cell eventually agrees. Rule 0, Rule 255 — all the boring ones.
Class II rules produce periodic structures. Stripes, diamonds, simple repeating patterns. Rule 90 from a single cell produces a perfect Sierpinski triangle — a fractal, but a predictable one. You can calculate any cell's value directly using XOR without simulating every step.
Class III rules produce chaos. Rule 30 from a single cell looks random. The center column passes every statistical test for randomness that anyone has thrown at it. Mathematica used it as a random number generator. Yet every cell is completely determined by the initial condition — there's no randomness in the mechanism at all. This is deterministic chaos in its simplest possible form.
Class IV is where things get strange.
Rule 110 sits between Classes II and III. It doesn't settle into repetition and it doesn't dissolve into noise. Instead, it produces persistent structures — triangular "particles" that propagate through a periodic background, colliding and interacting in complex ways.
In 2004, Matthew Cook proved that Rule 110 is Turing-complete. Any computation that can be performed by any computer — solving equations, running simulations, proving theorems — can be encoded as an initial pattern for Rule 110. The three-bit lookup table is sufficient for universal computation.
This is a startling result. The simplest possible rule that isn't trivial turns out to be as powerful as any computer ever built. Three bits in, one bit out, and that's enough.
Conway's Game of Life is the same idea in two dimensions. A cell looks at its eight neighbors instead of two. Born with exactly three, survives with two or three, dies otherwise. Four rules instead of a lookup table, but the same principle: local information, deterministic updates, global complexity.
Life is also Turing-complete. People have built computers inside the Game of Life — logic gates from glider collisions, memory from still lifes, clocks from oscillators. There exists a pattern in Life that simulates Life itself. The system can contain a copy of its own rules.
The R-pentomino preset is the best way to see this complexity in miniature. Five cells. After 1103 generations of chaotic expansion — tendrils reaching outward, collapsing, spawning new structures — it finally stabilizes into a configuration of still lifes, oscillators, and six escaping gliders. A five-cell initial condition producing over a thousand generations of irreducible computation before settling.
Lenia takes the discrete rules of Life and makes them continuous. Cells have real-valued states instead of binary. The neighborhood is a smooth kernel instead of the eight adjacent squares. The update rule is a continuous function instead of a threshold.
What's remarkable is that Lenia produces creatures — persistent, coherent structures that move, rotate, and interact. They look biological. Some pulse rhythmically. Some spin. Some orbit each other. The Orbium preset shows a smooth organism gliding across the canvas, maintaining its shape through continuous self-organization.
The transition from discrete to continuous doesn't reduce the complexity. If anything, it expands it. The space of possible Lenia rules is infinite (continuous parameters instead of 256 discrete options), and the creatures that emerge are far more varied than Life's gliders and spaceships.
Wolfram's classification and Cook's universality proof raise a question that still doesn't have a satisfying answer: why is Class IV possible?
Class I and II make intuitive sense — too much order suppresses information. Class III makes sense — too much chaos destroys it. But there's no obvious reason why a narrow band between them should support structures complex enough to encode arbitrary computation. The rules don't "know" about computation. They don't "try" to be interesting. They're lookup tables.
The same question appears everywhere: why does the Ising model produce fractal domains at exactly one temperature? Why does percolation produce scale-free clusters at exactly one probability? Why do three bits and a lookup table produce a universal computer at exactly one rule number?
The answer, if there is one, might be that computation and criticality are the same phenomenon viewed from different angles. At the critical point, a system processes information at all scales simultaneously — small perturbations can propagate to arbitrary distances, and the system's state depends on its entire history. That's not a bad definition of computation.
Rule 110 sits at the edge of chaos. The Ising model's critical point sits at the edge between order and disorder. The sandpile's self-organized criticality sits at the edge of stability. And all of them, at their edges, produce the same signature: structures at every scale, power-law distributions, and behavior that cannot be predicted without being simulated.
Maybe "computation" is just what criticality looks like when you ask it a question.