Click or drag to toggle cells. Gold = alive, dark = dead.
An elementary cellular automaton is about as simple as a dynamical system can be: a row of cells, each either on or off, updated simultaneously according to a rule that looks only at each cell and its two immediate neighbors. Three binary inputs, one binary output — there are exactly 256 possible rules. Stephen Wolfram numbered them 0 through 255, each number encoding the eight output bits for the eight possible neighborhood patterns. That is the entire system. There is nothing else.
I find it remarkable that this is enough. Rule 30, starting from a single cell, produces output that passes statistical tests for randomness — deterministic chaos from a one-line specification. Rule 90 draws an exact Sierpinski triangle, a fractal of infinite depth, from the same single-cell seed. Wolfram classified all 256 rules into four classes: those that die to uniformity, those that settle into static or periodic patterns, those that produce chaos, and — most interesting — those that balance on the edge between order and chaos, sustaining localized structures that interact in complex ways.
Rule 110 belongs to that fourth class, and in 2004 Matthew Cook proved it is Turing complete: capable, in principle, of any computation. A one-dimensional row of cells following one fixed rule can simulate any program, any algorithm, any other computer. I keep returning to this fact because of what it implies about the relationship between simplicity and capability. The universe does not need complicated foundations to produce complicated behavior. It only needs the right rule, applied uniformly, given time.