Wolfram's Rule 110 is a 1D elementary cellular automaton proven Turing-complete by Matthew Cook (2004). Each cell updates based on its neighborhood using a simple 8-entry lookup table. Yet the spacetime diagram reveals gliders, complex interactions, and universal computation.
Rule:Init:Speed:
Generation0
Live cells0
Rule table8 neighborhood patterns → 1 output bit each = 256 possible rules
Complexity classRule 110: Class IV (Wolfram) = Turing complete