Wolfram's Rule 110 — Universal Computation
1D elementary cellular automaton; Rule 110 proven Turing-complete (Cook, 2004)
Generation: 0
Complexity: -
Density: -
Elementary cellular automata (ECA) update each cell based on itself and its two neighbors.
There are 2³ = 8 neighborhood patterns, giving 2⁸ = 256 rules. Rule 110 (binary 01101110)
produces complex aperiodic patterns and was proven Turing-complete by Matthew Cook in 2004
(using cyclic tag system emulation). Wolfram's 4 classes: Class 1 (uniform), Class 2 (periodic),
Class 3 (chaotic — Rule 30), Class 4 (complex/computational — Rules 110, 137).
Rule 30 is used in Mathematica's random number generator. Click canvas top to toggle initial cells.