Elementary Cellular Automata

An elementary cellular automaton is the simplest possible computation that produces complex behavior. One dimension. Two states — black or white. A rule that looks at each cell and its two neighbors: three bits in, one bit out. Eight possible neighborhoods means eight binary outputs, which means 2⁸ = 256 possible rules. That is the entire space.

Some rules die to uniformity. Some produce repetition. Some produce randomness indistinguishable from noise. And a few — Rule 110 is the canonical example — produce structured complexity sufficient to be Turing complete. The boundary between order and chaos is where computation lives.

Notable Rules

Rule 30

Wolfram's discovery. Deterministic chaos from trivial rules. The center column passes every statistical test for randomness. Used as Mathematica's random number generator. Computationally irreducible.

Rule 110

Turing complete. Matthew Cook proved in 2004 that this single rule can simulate any computation. Complex localized structures (gliders) interact and propagate. The simplest known universal computer in one dimension.

Rule 90

Sierpinski triangle. Pure XOR of left and right neighbors. Produces an exact fractal, self-similar at every scale. Additive, linear, fully predictable. The opposite of Rule 30: a reducible computation.

Rule 184

Traffic flow model. Particles move right when unblocked, stop when blocked. Models single-lane traffic, ballistic annihilation, and majority voting. The simplest particle-conserving rule.

Computational Irreducibility

The deepest lesson of cellular automata is not that simple rules produce complex behavior — though they do. It is that for many systems, there exists no shortcut to their future states. You cannot predict the 1000th row of Rule 30 without computing all 999 rows before it. The rule is 8 bits. The output is incompressible. The only way to know what happens is to run it.

Wolfram calls this computational irreducibility. Some systems are their own fastest simulation. No external observer, however powerful, can outpace the system itself. Prediction requires computation at least as expensive as the process being predicted. The universe, in this view, is not following a blueprint — it is performing an irreducible computation, and the result is what we call time.

The 256 rules are a complete census of one-dimensional, two-state, nearest-neighbor universes. Most are boring. A few are profound. The boundary between them is not gradual.