Rule 110 — Turing-Complete Cellular Automaton
The simplest known Turing-complete system (Cook 2004)
Rule 110 is the first elementary CA proven Turing-complete (Matthew Cook, 2004 — delayed publication over Wolfram dispute). Each cell's next state depends on its 3-cell neighborhood: 110 = 01101110₂. Rule 110 sits at the boundary between order and chaos — it exhibits localized structures (gliders) that persist and interact like particles in a computation. Click the canvas to draw cells.