1D automata evolving over time — Rule 110 is Turing-complete (Cook 2004)
4
Generation: 0
Rule: 110
Live cells: 0
Elementary Cellular Automata (Wolfram 1983): a 1D binary string evolves one row at a time. Each cell's next state depends on its current state and two neighbors — 8 possible patterns, each mapped to 0 or 1, giving 2⁸ = 256 possible rules.
Rule 110 (Matthew Cook 2004): proved Turing-complete by embedding universal computation via gliders on an infinite repeating background. This makes it one of the simplest known Turing-complete systems. Wolfram's A New Kind of Science conjectured this; Cook proved it (nearly cost him his job due to NDA).
Rule 30 generates pseudo-random bits from the center column — used in Mathematica's default RNG. Rule 90 produces the Sierpiński triangle. Rule 184 models traffic flow with jam formation and propagation.