computability
Every interesting property is undecidable
It is the era when programmers first dream of tools that read code and certify its behavior — "does this program ever leak memory, always terminate, never output a secret?" Confront the general form of that dream. Take any nontrivial property of what a program computes — not of its text, but of its behavior — and prove that no algorithm can decide it for all programs. Reduce the halting problem to the property to show the wall is universal, not a gap awaiting a cleverer analysis. Get it wrong and a generation of tool-builders chases a perfect analyzer that provably cannot exist, or gives up on the sound approximations that can — this is why program analysis is forever a craft of conservative estimates.
Who this problem belongs to
The two figures whose methods fit it best, out of 41 in contention.
Turing's 1936 proof that the halting problem is undecidable is the exact tool this problem asks to wield: reduce an arbitrary nontrivial semantic property of a program's behavior to the halting question, and the impossibility transfers. Rice's theorem, proved in 1953, is a direct generalization of Turing's own reduction technique, and the diagonalization argument Turing used to show no machine can decide its own halting is structurally identical to what a general undecidability proof for program properties requires. He personally invented the universal machine, the notion of a program as data, and the reduction method that makes 'this property is as hard as halting' a meaningful sentence. The theorem bearing Rice's name is Turing's method applied one level up.
Hoare's axiomatic semantics for program correctness (1969), the logic that lets a programmer formally prove a piece of code meets its specification, is the direct practical confrontation with the wall Rice's theorem erects: Hoare logic works precisely because it targets specific, tractable proof obligations rather than attempting the general, undecidable verification problem Rice rules out entirely. Hoare understood better than almost anyone on this roster why sound, general-purpose program verification tools must be conservative and incomplete — his entire career built the disciplined workaround to exactly this impossibility. His quicksort algorithm and his 'billion-dollar mistake' reflection on null references both show deep, hard-won engagement with what can and cannot be guaranteed about real software's behavior. He did not prove Rice's theorem but lived its consequences.
In the mind map
The same ideas, as concepts rather than history — in John's ML knowledge map.
41 figures are scored on this problem. Draw it in a battle to see where you land.