The simplest known Turing-complete 1D elementary CA
Rule 110 is an elementary cellular automaton (ECA) — a 1D grid of cells, each either 0 or 1, updated in lockstep. The next state of each cell depends on its current state and its two neighbors: 3 bits → 8 possible patterns → the rule maps each to 0 or 1.
Rule 110 maps: 111→0, 110→1, 101→1, 100→0, 011→1, 010→1, 001→1, 000→0 (binary 01101110 = 110).
Matthew Cook proved in 2004 (published with Wolfram's approval after a decade-long delay) that Rule 110 is Turing complete — it can simulate any computation. The proof uses Rule 110 to simulate a tag system, which simulates a 2-counter machine. Complex gliders and collisions encode computation.
Rule 110 lies at the edge of chaos (Class 4 in Wolfram's classification): neither static nor random — it supports persistent localized structures (gliders) that interact.