Rule 110 — a universal cellular automaton

Parent: famous-machines

Not a Turing machine but a computation-universal system almost too simple to believe.

The setup. A 1-D row of cells, each 0/1, updated in parallel: each cell's next value depends only on itself and its two neighbours (2³ = 8 input patterns). Numbering the 8 outputs as a binary byte gives the rule's name — Rule 110 is one specific such byte.

Cook (from Wolfram): Rule 110 is Turing-complete

By encoding gliders (moving patterns) that collide to carry and process information, Rule 110 can simulate any Turing machine (via cyclic tag systems).

Why it's famous. It's among the simplest known universal systems — a fixed 8-bit local rule with no state, no head, just parallel neighbour-updates — yet full computation. It's the headline evidence for Wolfram's thesis that universality (and undecidability) is the rule, not the exception: even trivial-looking dynamics can be computationally universal, hence have undecidable long-run questions.