Rule 110 is an elementary 1D cellular automaton where each cell's next state depends on itself and its two neighbors — 8 possible patterns, encoded as the rule number in binary. Wolfram classified rules into 4 classes; Rule 110 is Class IV (complex). In 2004, Matthew Cook proved Rule 110 is Turing complete, meaning it can compute anything a computer can, emerging from three simple states. It exhibits a mix of stable structures, periodic oscillators, and moving gliders — the hallmarks of complex computation from minimal rules.