09 · Computability

This is the first hearing of Part II. Computation stops being the witness and takes the examiner's chair — and its first question is aimed at itself: what does its own founding limit actually prove?

What do the limits of computation prove about the limits of reason?

Two papers settled the same question six weeks apart in 1936, and neither author had read the other's proof. Alonzo Church's "An Unsolvable Problem of Elementary Number Theory" appeared on 15 April in the American Journal of Mathematics (58: 345–363), showing by lambda-definability that no algorithm decides the Entscheidungsproblem — the question, posed by David Hilbert and Wilhelm Ackermann in Grundzüge der theoretischen Logik (1928), of whether a mechanical procedure could certify the validity of any first-order sentence. Alan Turing's own paper, "On Computable Numbers, with an Application to the Entscheidungsproblem," was received by the Proceedings of the London Mathematical Society on 28 May — and reached the identical negative answer by an entirely different route: a human clerk idealized down to a paper tape, a finite set of states, and a table of instructions. Turing, disappointed to learn he had been beaten to publication, added an appendix proving that his machines and Church's lambda-definable functions compute exactly the same class of functions. Two definitions of "mechanical," invented independently, turned out to coincide exactly. That coincidence is the whole of the evidence for what is now called the Church–Turing thesis, and evidence is not the same thing as proof.

It cannot be a theorem, because "effectively calculable" was never a formal term before Turing formalized it — you cannot prove an identity between something precise and something that, until that moment, was only an intuition. What Turing actually did was analyze, by exhaustion, everything a human "computer" — a person following fixed instructions with pencil and paper — could do: read a symbol, change an internal state, write a symbol, shift attention. Every rival formalism proposed since — Gödel–Herbrand's general recursive functions, Emil Post's production systems, register machines — has been proven equivalent to Turing's, and Stephen Kleene, who named the conjecture "Church's Thesis" in 1943, treated that convergence as inductive support rather than deductive closure. So the thesis sits in a category Hilbert's program never anticipated: not quite mathematics, not quite empirical science, held up by the fact that everyone who has tried to break it has instead confirmed it.

That instability is itself philosophically productive, because the method Turing used to reach it — diagonalization, turning a system's own machinery against itself — outgrew the theorem it built. Cantor used it in 1891 to show no list of real numbers can be complete; Gödel adapted it in 1931 to build an arithmetical sentence that asserts its own unprovability; Turing adapted it again to show no algorithm can decide, for an arbitrary program, whether it halts — feed a hypothetical halting-decider its own description and a contradiction falls out in one line. The same skeleton reappears in Tarski's proof that no sufficiently rich language can define its own truth predicate, and in Frederic Fitch's 1963 paradox of knowability. Diagonalization stopped being a mathematician's trick around the middle of the twentieth century and became philosophy's standard proof that a system cannot fully turn its lights on itself — the argument form this book's own courtroom spine depends on.

It is also the argument form behind the most publicized claim in this territory. J. R. Lucas told the Oxford Philosophical Society in 1959, and then argued in print in "Minds, Machines and Gödel" (Philosophy 36, 1961: 112–127), that Gödel's theorem refutes mechanism: for any consistent formal system F strong enough to encode arithmetic, Gödel's construction yields a true sentence F cannot prove, yet a human reasoner, standing outside F and reflecting on it, can see that the sentence is true — so no single formal system captures everything a mind can know, and minds are therefore not machines. Roger Penrose revived the argument at greater length in The Emperor's New Mind (1989) and defended a reinforced version in Shadows of the Mind (1994). The standard reply, developed across decades of responses from Paul Benacerraf onward, is that the argument smuggles in exactly the certainty Gödel's second incompleteness theorem forbids: to "see" that the Gödel sentence for F is true, the reasoner must already know F is consistent, and no consistent system — human or mechanical — can prove its own consistency from within. The argument also assumes a human mind is well modeled as one single, fixed, consistent formal system in the first place, which nothing here establishes. Computation, examining this claim on its own witness stand, cannot certify it; but philosophy answers back here too, because the machine's own founding thesis has the identical shape of unprovable self-trust — the Church–Turing thesis cannot certify its own domain without appealing to an intuition about "mechanical" that no formalism proves, any more than the human reasoner can certify F's consistency from inside F.

Turing knew his own thesis had an edge, because he drew it himself. His 1939 Princeton doctoral thesis, "Systems of Logic Based on Ordinals," introduced oracle machines: Turing machines equipped with a black-box oracle answering questions no Turing machine could resolve unaided. B. Jack Copeland and Diane Proudfoot later named the research program built on that opening "hypercomputation," and Copeland has argued that exotic physical setups — closed timelike curves, or the infinite-proper-time computations permitted in a Malament–Hogarth spacetime — might in principle realize an oracle. The honest objection is the verification problem: even if such a device were built, nothing from outside could ever confirm it had computed a genuinely non-Turing-computable function rather than an extremely large Turing-computable one. Here physics, not logic, casts the deciding vote on whether the thesis bounds all possible computation or only computation as our universe happens to permit it.

Gödel himself licensed far less than his popularizers claim. In his 1951 Gibbs Lecture he stated a disjunction and stopped there: either the human mind is not equivalent to any finite machine, or there exist mathematical problems absolutely undecidable by any means — or both — but he refused to say which, remaining a mathematical Platonist who suspected the first disjunct without ever asserting he had proved it. What Gödel proved is a limit inside formal systems; what Lucas, Penrose, and a century of secondary literature have drawn from it is a conclusion about minds that the theorem itself never reaches.

Connections

Chapter 00 named 1936 as the moment the machine fell out of a philosophical proof; this chapter returns to ask what that moment actually licenses. Chapter 01 owns Gödel and Curry–Howard as logic's shared inheritance. Chapter 04 owns the question the Lucas–Penrose argument tries to settle from outside — whether the mind is what the brain computes. Chapter 10 tightens "in principle" into a measurable resource. Chapter 12 shows what proof assistants do with incompleteness once it is treated as an engineering constraint rather than a philosophical verdict.

Open questions

Is the Church–Turing thesis falsifiable — and would a working hypercomputer refute it, or merely relocate the boundary it draws? Does Gödel's 1951 disjunction ever get resolved, or does it stay open the way the thesis itself does? And if minds turn out to be Turing-equivalent, does that settle functionalism, or only computability — a question this chapter can raise but not answer.

Go deeper

• B. Jack Copeland, Carl J. Posy, and Oron Shagrir, eds., Computability: Turing, Gödel, Church, and Beyond (Cambridge, MA: MIT Press, 2013).
• Alonzo Church, "An Unsolvable Problem of Elementary Number Theory," American Journal of Mathematics 58 (1936): 345–363; Alan Turing, "On Computable Numbers, with an Application to the Entscheidungsproblem," Proceedings of the London Mathematical Society, ser. 2, 42 (1936–37): 230–265, received 28 May 1936 — doi.org/10.1112/plms/s2-42.1.230.
• Stanford Encyclopedia of Philosophy, "The Church-Turing Thesis" — plato.stanford.edu/entries/church-turing.