computability
Three machines, one class
It is the mid-1930s, and "computable" is being defined independently three times over — as an idealized machine reading a tape, as a calculus of pure function substitution, as recursively defined number-theoretic functions — by people who suspect, but have not shown, that they are talking about the same thing. Prove the equivalence: that these utterly different formalisms pick out exactly one class of functions, and argue why that class deserves to be called "everything effectively computable." The thesis cannot be proved, only defended, and the equivalence is the defense. Get it wrong and the theory of computation fractures into rival notions with no agreement on what a computer even is — instead, this convergence becomes the bedrock the field rests on.
Who this problem belongs to
The two figures whose methods fit it best, out of 41 in contention.
Turing is one of the three inventors this problem asks about. His 1936 paper 'On Computable Numbers' defines the Turing machine — an idealized device reading and writing symbols on an infinite tape according to a finite table of rules — and proves, in an appendix written after seeing Church's lambda-calculus paper, that his machine-computable functions coincide exactly with Church's lambda-definable ones. He personally supplied the equivalence argument for two of the three formalisms and, crucially, argued why 'machine-computable' is the right formalization of 'effectively calculable' at all — an intuitive, unprovable claim he defended by exhausting every mechanical procedure a human computer could carry out by hand. No one on this roster is closer to having personally built and defended this exact result.
Von Neumann understood the significance of Turing's and Church's work with unusual speed and depth, personally corresponding with Turing (who spent 1936-38 at Princeton, partly under von Neumann's orbit) and later crediting Turing's universal machine as the conceptual basis for the stored-program computer architecture that bears traces of his name. His own contributions to mathematical logic, set theory, and the foundations of mathematics — including work adjacent to the Hilbert program that Godel's and Turing's results undermined — gave him genuine command of the formal apparatus needed to judge the equivalence claims. He did not personally author the proof that Turing machines, lambda calculus, and recursive functions coincide, but few contemporaries understood its implications for real machine design as clearly or as immediately as he did.
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.