Rule 110 — Universal Computation

Rule 110 is a 1D elementary cellular automaton that is Turing-complete (Matthew Cook, 2004). Each cell is determined by itself and two neighbors. Despite the simplicity, complex emergent patterns arise — gliders, collisions, structures without limit.

Controls

Cell size (px) 2

Speed (rows/frame) 1

Initial condition

Rule lookup table

Rule #110

Generation0

Width—

Rule 110 is Turing-complete (Cook 2004). Proof uses tag systems embedded in glider collisions. Wolfram NKS: simple rules → complex behavior → universality.