Turing's proof

Lore & Background

Turing's proof relies on his development of typewriter-like 'computing machines' that obey a simple set of rules and his subsequent development of a 'universal computing machine'. The proof consists of three parts: first, that no computing machine can decide whether an arbitrary computing machine is 'circle-free' (i.e., prints its number forever); second, that no machine can determine whether a given machine ever prints a given symbol; third, that if there were a general method for determining provability of a formula, then there would be a general method for determining whether a machine ever prints 0. The third proof uses formal logic and a reductio ad absurdum to conclude that the Hilbert Entscheidungsproblem can have no solution.

Reader's Guide

Turing's proof is significant because it definitively answered Hilbert's Entscheidungsproblem in the negative, showing that there are mathematical yes–no questions that cannot be solved by any algorithm. The proof introduced the concept of a universal computing machine, a theoretical foundation for modern computers. It also established the undecidability of the halting problem (via the first proof) and anticipated Rice's theorem (via the second proof). The proof's constructive nature—describing a real, buildable machine—was essential to its reductio ad absurdum argument. By demonstrating that no general method exists for deciding provability in Principia Mathematica, Turing's work complemented Gödel's incompleteness results and laid the groundwork for computability theory.

Did You Know?

• Turing's proof was the second proof of the negation of Hilbert's Entscheidungsproblem, after Church's theorem.
• The proof shows that no computing machine can decide whether an arbitrary computing machine is 'circle-free'.
• Turing's third proof uses a reductio ad absurdum in only 64 words and symbols.
• The proof relies on a 'universal computing machine' that can simulate any other computing machine.

Confronting Hilbert's Dream

Published the following year under the title 'On Computable Numbers, with an Application to the Entscheidungsproblem,' this document delivered the second independent refutation—following Church's theorem—of Hilbert's conjecture that every purely mathematical yes-or-no question could, in principle, be settled by computation. Turing's target was precise: he demonstrated that certain decision problems are undecidable, meaning no single algorithm can infallibly return a correct yes-or-no answer for every possible instance of the problem. Crucially, he set his achievement apart from Gödel's well-known results, insisting his proof was quite different in character. His specific claim was that no universal procedure exists that can determine whether a given formula is provable within Principia Mathematica. In doing so, he shifted the conversation from what can be proved to what can be computed—and demonstrated that the latter boundary is narrower than many had hoped.

Three Proofs, One Architecture

Turing did not deliver a single monolithic argument. Instead, he stacked three proofs in careful dependency: the second and third both lean on the first, and all three rest on his invention of simple rule-governed computing machines and the universal machine that could simulate any of them. The first proof establishes that no machine can decide, in a finite number of steps, whether an arbitrary machine will run forever without halting—what we now call the halting problem. The second generalizes the idea: no single evaluator can inspect any machine's program and predict whether that machine will ever emit a particular symbol, a result later recognized as Rice's theorem. The third proof bridges the gap to formal logic. For every computing machine, Turing constructs a corresponding formula and shows that if a general method existed for deciding the formula's provability, then a general method would also exist for deciding whether the machine ever prints a given symbol—contradicting the second proof. The entire edifice closes with a reductio ad absurdum expressed in a mere sixty-four words and symbols, declaring Hilbert's Entscheidungsproblem unsolvable.

The Machine That Simulated All Machines

At the heart of Turing's argument lies a simple device: a typewriter-like machine that reads and writes symbols on a tape, obeying a fixed set of rules. From this starting point he built the universal computing machine, capable of mimicking the behavior of any other machine in the family. Each machine is identified by a Standard Description, a string drawn from the alphabet of A, C, D, L, R, N, and a semicolon. Turing showed that any such string can be converted into a base-8 integer and back again, giving every machine a unique numerical address. In the first proof, a composite machine called H takes an arbitrary integer, translates it into a Standard Description, and feeds it to an embedded decision subroutine D. H then simulates the target machine's motions, extracts a single binary figure at a predetermined position, and prints it as part of a diagonal sequence. After each simulation H tidies its tape, increments the counter, and moves to the next number. The machines under test produce endless streams of binary figures—ones and zeros—and H reads across them, one row at a time, building a number that no machine in the sequence could generate.

A Proof Built by Construction

What makes Turing's argument feel almost physical is its insistence on construction. Rather than appealing to abstract set theory or pure logic, he spends much of the paper describing machines in enough detail that one could, in principle, actually build them. This concreteness is not a stylistic flourish; it is structurally necessary. Because the proof proceeds by reductio ad absurdum, Turing must first demonstrate that every machine he invokes is genuinely realizable. The only element that resists construction is the decision machine D—the hypothetical device that, given any Standard Description, would declare the target machine satisfactory or unsatisfactory. The entire argument exists to show that D cannot exist. Turing deliberately withholds any explanation of D's internal workings, noting that for the purposes of the proof it does not matter whether D uses heuristics, pattern-matching, or some other strategy. The mathematics required is modest. The real force of the argument lies in the diagonal construction: Turing's machine H cannot compute its own number, let alone the full diagonal number, and the fallacy in any opposing argument rests on the unjustified assumption that such a diagonal number is itself computable.