Halting problem
Named by 4 essays across 2 fields — each of them below, with the objects they name alongside 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.
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.
The machines that need a reason never to stop
Run every three-state machine on a blank tape and the ones that halt announce themselves: the longest stops after 21 steps. The work is in the others. Each needs a reason it will never stop, and four simple kinds of reason settle all but 27 of them — machines that sweep back and forth over a growing tape and defeat every check that looks for a repeat.
Dominoes that no algorithm can match
Emil Post's puzzle has no machines and no programs in it: a handful of dominoes, each with a string on top and a string underneath, and the question whether some row of them, repeats allowed, spells the same word along both edges. No algorithm can answer it for every set of dominoes, because a set can be built whose only matches are a machine's run written out twice, one step out of phase — and three dominoes with strings of three characters already need thirty-six in a row before the edges agree.
Named alongside it
The objects these essays reach for when they reach for this one.
Busy beaverTuring machineUndecidabilityComputationExhaustive searchReductionBreadth-first searchCellular automatonComputer-assisted proofDecidabilityGliderIteration