Definition
Plain language
A famous simple rule for evolving rows of cells that turns out to be capable of universal computation.
As stated in the literature
A one-dimensional, two-state cellular automaton proven Turing-complete; used as a clean test bed for isolating sequential reasoning depth from storage capacity in long-context model experiments.
Why it matters: It's a clean, minimal test bed for asking whether a model can reason through deep sequential steps without secretly relying on memorized shortcuts.
For example, starting from a single dark cell on an otherwise empty row and repeatedly applying Rule 110, you eventually see intricate patterns capable, in principle, of simulating any computer.
Heard on the show
“They use something called Rule 110, which is a cellular automaton — a row of cells, each zero or one, that evolves in discrete time steps according to a fixed rule.”Episode 085 — Why Long-Context Models Might Need Compute, Not Capacity, Before Eviction