computability
Will it ever halt?
It is 1936, and the dream on the table is a mechanical procedure that can decide any mathematical question — Hilbert's vision of an automatic mathematics. Your task sounds modest: write a program that takes any program and its input and decides whether it will eventually halt or run forever. Either build it, or prove — rigorously, once and for all — that no such program can exist. This is not an engineering nuisance a faster machine could fix; it is a hard limit on computation itself, defining the boundary of what any computer, ever, can do. Get it wrong and you chase an impossible tool forever, or wrongly declare whole classes of problems hopeless — the proof of impossibility is a founding act of computer science.
Who this problem belongs to
The two figures whose methods fit it best, out of 44 in contention.
This is, almost literally, Turing's 1936 paper. 'On Computable Numbers' invented the abstract machine the problem presupposes, defined computability through it, and proved the Entscheidungsproblem unsolvable by a diagonal argument over machine descriptions — the halting-style argument is his native move. He had exactly the tools the problem demands and nothing more was needed: Cantor's diagonalization, Gödel's arithmetization of syntax as precedent, and the crucial conceptual step of a universal machine that can simulate any machine from its description. That universality is what makes self-reference bite: feed a purported halting decider a program built from its own description and derive contradiction. Church reached the same limit via lambda calculus that year, but Turing's machine model is the one that made the impossibility feel physical. Ceiling case, by construction.
Cook works one level up from 1936 — his 1971 theorem concerns feasibility (SAT's NP-completeness) rather than computability — but the technical machinery is directly ancestral to and descended from this problem. His proof arithmetizes Turing machine computations into logical formulas, exactly the encode-computation-as-syntax move a halting-problem proof requires; anyone who can simulate an arbitrary nondeterministic machine inside propositional logic can run the diagonal argument in his sleep. Reductions between problems, the core habit of his career, are the standard way undecidability spreads from halting to everything else (via Rice-style and many-one reductions). The era gap runs backward gracefully: nothing Cook relies on postdates 1936 except notation. He would not invent the question, as Turing did, but he would settle it rigorously and recognize its structure immediately. Among the strongest here.
In the mind map
The same ideas, as concepts rather than history — in John's ML knowledge map.
44 figures are scored on this problem. Draw it in a battle to see where you land.