Busy beaver
Named by 3 essays across one field — each of them below, with the objects they name alongside it.
Also named here as turing machine — the same set of essays touches all of them, so they are one junction rather than several.
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.
Halting problemTuring machineExhaustive searchReductionUndecidabilityBreadth-first searchComputationComputer-assisted proofDecidability