Concept

Computation

A process that transforms an input into an output by a finite sequence of mechanical steps, each fixed by a rule. Models of computation such as Turing machines and cellular automata make precise which problems such a process can solve and at what cost.

Named by 2 essays across one field — each of them below, with the objects they name alongside it.

Elementary cellular automaton, rule 110. A row of cells evolving downward, each cell decided by the three above it.

The rule that computes

One of the 256 elementary rules can run any program. Not simulate one, not approximate one — a machine that can compute anything computable, built from a lookup table with eight rows and nothing else.

dynamics · Cellular automata

A local rule taking a vote. A space-time diagram of the GKL rule on 149 cells from a random row with 69 ones. Black and white regions grow and meet along slanting boundaries, and after 69 steps the whole ring is 0.

No local rule can count the votes

A ring of cells, each holding 0 or 1, has to agree on whichever value is in the majority — every cell seeing only its neighbours. The best-known rule gets it right most of the time and wrong near a tie; no rule of any radius gets it right always. Yet two rules run one after the other do, on every ring, and the first of them is the traffic rule.

dynamics · Cellular automata

Named alongside it

The objects these essays reach for when they reach for this one.

Cellular automaton Locality Counterexample Decision procedure Determinism Exhaustive search Glider Halting problem Impossibility Iteration Majority Rule 110

All concepts