Rule 110 — Universal Cellular Automaton

Rule 110 (Wolfram 1986): each cell's next state determined by its left neighbor, itself, and right neighbor. The rule number (110 = 01101110₂) encodes outputs for all 8 three-cell patterns. Matthew Cook (2004) proved Rule 110 is Turing complete — it can simulate any computation — by showing it supports gliders that implement a tag system equivalent to a universal Turing machine. Gliders, stationary backgrounds, and their collisions implement logical operations.