Elementary Cellular Automaton — Rule 110
The simplest known Turing-complete system (Cook 2004)
Rule 110 is an elementary 1D cellular automaton where each cell's next state depends
only on itself and its two neighbors (8 possible patterns → 2⁸ = 256 rules numbered 0–255).
Rule 110's binary encoding: 01101110₂ = 110.
Matthew Cook proved in 2004 (delayed by Wolfram's legal action) that Rule 110 is
Turing complete — it can simulate any computation using gliders and their collisions,
analogous to Conway's Game of Life. The proof uses Rule 110 to simulate a cyclic tag system.
Unlike Rule 30 (random) or Rule 90 (self-similar), Rule 110 lives at the boundary between
order and chaos — Wolfram's "Class IV" complexity.