The simplest known Turing-complete 1D system — complex behavior from nearest-neighbor rule
1D nearest-neighbor CAs with 2 states, 3 neighbors → 256 possible rules, classified by Wolfram:
Class I/II: fixed/periodic (Rules 0, 4, 108...)
Class III: chaotic, random-looking (Rule 30 — used in Mathematica RNG)
Class IV: complex, localised structures (Rule 110, Game of Life)
Rule 110 (Cook 2004): Turing complete — gliders interact to simulate cyclic tag systems, which simulate Turing machines. Click canvas to toggle cells.