Cellular Automata

What you're looking at

What are elementary cellular automata?

A single row of cells, each either alive or dead. To compute the next generation, look at each cell and its two neighbors — that's a 3-cell neighborhood with 8 possible patterns. A "rule" assigns an output (alive or dead) to each pattern. Since there are 8 patterns and each can map to 0 or 1, there are 2⁸ = 256 possible rules. The rule number is just that output pattern read as a binary number. That's it — start with one row, apply the rule, get the next row. Repeat.

Why Rule 110 matters

In 2004, Matthew Cook proved that Rule 110 is Turing-complete — it can compute anything a general-purpose computer can, given the right initial conditions and enough space. From a trivially simple rule acting on a 1D grid, you get universal computation. That's a remarkable result. It means the boundary between "trivial" and "capable of arbitrary computation" is much thinner than you'd expect.

Wolfram's four classes

Stephen Wolfram categorized all 256 rules into four classes based on their long-term behavior. Class I: everything dies or goes uniform (e.g., Rule 0). Class II: simple periodic structures (e.g., Rule 184). Class III: chaotic, pseudo-random patterns (e.g., Rule 30). Class IV: complex structures that interact — localized patterns, gliders, long transients (e.g., Rule 110). The interesting stuff lives at the boundary between order and chaos.

Where this shows up

Wolfram's "A New Kind of Science" (2002) made the argument that simple programs — not equations — are the right way to model natural complexity. Whether or not you buy the full thesis, the core observation holds: simple local rules produce global complexity. Cellular automata show up in modeling traffic flow, crystal growth, biological pattern formation, and pseudorandom number generation (Rule 30 was used in Mathematica's random number generator for years). The deeper lesson is about emergence — complex behavior doesn't require complex rules.