computability
The fastest-growing function
It is the era when computability theory hunts for the concrete edge of the uncomputable. Consider the busy-beaver function: among all halting programs of a given size, the maximum number of steps any of them runs before stopping. It is perfectly well-defined and grows faster than any function a computer can calculate — for even modest sizes its values dwarf anything nameable, and beyond a point they become independent of mathematics itself. Prove it is uncomputable, and explain why: a machine that could compute it could solve the halting problem. Get the lesson wrong and you treat "uncomputable" as an abstraction with no teeth, missing that it has a face — a small function whose values are provably beyond all calculation, forever.
Who this problem belongs to
The two figures whose methods fit it best, out of 46 in contention.
The busy-beaver function is a direct descendant of Turing's own 1936 machinery. His universal machine and his proof that no algorithm decides whether an arbitrary machine halts are exactly what makes the busy-beaver values uncomputable: knowing them for large enough sizes would let you decide halting by comparison, contradicting his own theorem. Turing built the formal notion of a Turing machine that Tibor Rado's 1962 busy-beaver definition uses outright, and the reduction argument this problem demands — a busy-beaver oracle solves the halting problem — is a direct corollary of Turing's construction, not merely an application of it. He predates Rado's specific formulation by decades but supplies literally every conceptual and formal piece the proof needs.
Moore's textbook The Nature of Computation treats the busy-beaver function as a signature example precisely because it makes uncomputability concrete and vivid — a specific, well-defined, rapidly growing function whose values are provably beyond calculation — and he explains the halting-problem reduction argument this problem's proof requires with characteristic clarity. His research connecting computational hardness to statistical-physics phase transitions depends on a deep, working fluency with exactly this kind of diagonalization and reduction reasoning. Writing decades after Rado's 1962 definition, Moore did not originate the busy-beaver function, but few living researchers explain, teach, and rely on its proof more precisely or more often, making him an outstanding fit for this problem despite not being its historical author.
In the mind map
The same ideas, as concepts rather than history — in John's ML knowledge map.
46 figures are scored on this problem. Draw it in a battle to see where you land.