Simple Rules, Complex Worlds
A cellular automaton is a grid of cells that evolves by purely local rules — each cell looks only at its immediate neighbors to decide its next state. Yet from this simplicity, staggering complexity emerges: fractals, turbulence-like chaos, self-replicating structures, and even universal computation. Stephen Wolfram's systematic exploration of all 256 elementary (1D, binary, radius-1) rules revealed that complexity is not a product of complicated rules but of the right simple ones.
The Wolfram Classification
Wolfram grouped the 256 elementary rules into four behavioral classes. Class I rules collapse to uniform states. Class II rules produce periodic, predictable patterns. Class III rules generate chaotic, apparently random output (Rule 30 is the archetype). Class IV rules — the 'edge of chaos' — produce the most fascinating behavior: localized structures that propagate, collide, and interact, reminiscent of particles in physics.
Computation at the Edge
Rule 110, a Class IV automaton, was proven Turing-complete by Matthew Cook in 2004. This means a one-dimensional grid of binary cells, updating by a trivially simple lookup table, can in principle compute anything a laptop can. The proof works by encoding a cyclic tag system — a known universal computation model — into Rule 110's glider collisions. It is perhaps the most striking demonstration that complexity and computation require almost no ingredients.
Beyond One Dimension
Two-dimensional CAs, most famously Conway's Game of Life, exhibit even richer behavior: glider guns, self-replicating patterns, and engineered Turing machines built entirely from cellular interactions. CAs have found practical application in modeling traffic flow, crystal growth, wildfire spread, and lattice-gas fluid dynamics, bridging the gap between abstract computation theory and physical simulation.