Matpic
mathematics, in pictures
Concept

Halting problem

The question whether a given program, run on a given input, eventually stops. Turing proved that no algorithm answers it correctly for every program, by a diagonal argument, and most other impossibility results about programs are reduced to it.

Named by 2 essays across 2 fields — 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 All 20,736 two-state Turing machines, by when they halt. A bar chart of the two-state, two-symbol Turing machines by halting step on a blank tape: 1: 6912, 2: 2304, 3: 384, 4: 128, 5: 16, 6: 40, never: 10952.

No algorithm can read what a program does

Whether a program halts cannot be decided by any algorithm. Henry Rice showed in 1953 that the halting problem is not special: no algorithm can decide any property of what a program does — whether it ever prints a 7, whether it computes the successor function, whether it is a virus — except the two properties that hold of every program or of none. Every one of the 20,736 smallest Turing machines can be checked by hand; the theorem says why that stops.

logic · Diagonalisation

Named alongside it

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

ComputationUndecidabilityBusy beaverCellular automatonExhaustive searchGliderIterationLocalityReductionRule 110Turing machineUniversality

All concepts