What you're looking at
An elementary cellular automaton is the simplest interesting computational
universe: an infinite row of cells, each black or white, updated in discrete time steps.
A cell's next state depends only on itself and its two neighbours — three bits in,
one bit out. There are 23 = 8 possible neighbourhoods and
28 = 256 possible rules. That's the whole zoo.
Stephen Wolfram catalogued all 256 in the 1980s and, in 2002, published A New Kind of Science. The provocative claim: from rules so trivial you can write them on a napkin, you get nested fractals (rule 90), pure randomness that passes statistical tests (rule 30), and full Turing-complete computation (rule 110, proved by Matthew Cook). The argument is that nature might be doing the same thing — simple local rules, complex global behaviour — and that this changes how we should think about modelling, complexity and physics.
The numbering convention is Wolfram's: write the rule as an 8-bit binary number where bit
i is the output for neighbourhood i (with i read as
left·centre·right in binary). Rule 30 is 00011110; rule
110 is 01101110. Try them. The diagram above the canvas shows the eight
transitions for whichever rule is loaded.
A note on the edges. The universe is infinite but the canvas isn't. Wrap (the default, and the NKS convention) joins the left and right edges into a ring — so once the pattern grows wider than the grid, it folds in from the other side and "things appear on the left." Zero and One instead pretend everything outside the canvas is permanently white or black, which gives you a clean view of the central triangle.
A few rules worth trying
- Rule 30 — from a single black cell, produces a stream of bits so statistically random that Wolfram used it as the random number generator in Mathematica for years.
- Rule 90 — the Sierpinski triangle, derived purely from XOR of two neighbours.
- Rule 110 — the famous one. Cook proved it is Turing-complete: you can in principle compute anything with it.
- Rule 184 — a minimal traffic-flow model. Try it with a random initial condition.
- Rule 54 — complex localised structures (gliders) on a periodic background. Still not fully understood.
Where this comes from
- A New Kind of Science — the full book, free online.
- MathWorld: Elementary Cellular Automaton — the canonical reference.
- The Wolfram Atlas — deep dive into each of the 256 rules.
- Wikipedia: Elementary cellular automaton — classification, history, references.
- Rule 110 — Turing completeness — Cook's proof.
- Wolfram's 15-year retrospective — what he thinks held up.