Busy beaver
Named by 2 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.
Named alongside it
The objects these essays reach for when they reach for this one.
Exhaustive searchHalting problemTuring machineComputationComputer-assisted proofDecidabilityReductionUndecidability