← All Labs

Rule 110 — Turing Complete CA

The elementary cellular automaton proven Turing complete — complex patterns from a 3-cell rule

Rule 110 lookup table (111→0, 110→1, 101→1, 100→0, 011→1, 010→1, 001→1, 000→0)
Rule 110 (binary 01101110): next state depends on left, center, right neighbors. Proven Turing complete by Matthew Cook in 2004 — any computation can be encoded in initial conditions. Glider-like structures emerge and interact. Click on the bottom row to flip cells, then run the automaton. The spacetime diagram scrolls upward as time progresses.