Turing Completeness — Rule 110

Elementary cellular automaton proven Turing-complete (Cook, 2004)
Live cell
Dead cell
→ Time flows downward
Rule number110
Cell size4
Rule 110 is a 1D cellular automaton where each cell depends on its left neighbor, itself, and right neighbor. Matthew Cook (2004) proved it is Turing-complete — capable of universal computation. The glider patterns (moving structures) interact like logic gates. Rule 30 generates pseudo-randomness (used in Mathematica); Rule 90 produces the Sierpinski triangle.