Turing's proof
Proof that some mathematical questions cannot be answered by computation.
Turing's proof, submitted by Alan Turing on 12 November 1936 and first published in 1937 under the title "On Computable Numbers, with an Application to the Entscheidungsproblem," was the second demonstration (following Church's theorem) that Hilbert's Entscheidungsproblem is false. This problem was the conjecture that every purely mathematical yes–no question can be answered by computation; more precisely, it held that for any decision problem, a single algorithm exists that can infallibly produce a correct "yes" or "no" for every instance. Turing's work showed that some such problems are undecidable. As Turing himself put it: "what I shall prove is quite different from the well-known results of Gödel ... I shall now show that there is no general method which tells whether a given formula U is provable in K [Principia Mathematica]."
Turing followed this initial proof with two others, both of which depend on the first. All three rely on his invention of typewriter-like "computing machines" that follow a simple set of rules, and on his subsequent creation of a "universal computing machine."
In his proof that the Entscheidungsproblem has no solution, Turing worked through two earlier proofs that led to his final one. His first theorem is most directly related to the halting problem, while the second is more relevant to Rice's theorem.
The first proof shows that no "computing machine" can decide whether an arbitrary "computing machine" (represented by an integer 1, 2, 3, ...) is "circle-free"—that is, whether it continues printing its binary number forever. Turing stated: "...we have no general process for doing this in a finite number of steps." Although the proof appears to use a diagonal argument, it actually demonstrates that the machine (called H) cannot compute its own number, let alone the entire diagonal number from Cantor's diagonal argument. Turing noted: "The fallacy in the argument lies in the assumption that B [the diagonal number] is computable." The proof does not require advanced mathematics.
The second proof is more familiar to readers as Rice's theorem: "We can show further that there can be no machine E which, when supplied with the S.D ["program"] of an arbitrary machine M, will determine whether M ever prints a given symbol (0 say)."
The third proof states: "Corresponding to each computing machine M we construct a formula Un(M) and we show that, if there is a general method for determining whether Un(M) is provable, then there is a general method for determining whether M ever prints 0." This proof uses formal logic to establish a first lemma, followed by a brief word-proof of the second. Finally, in just 64 words and symbols, Turing proves by reductio ad absurdum that "the Hilbert Entscheidungsproblem can have no solution."
Turing created many abbreviations in his paper. He spent much of it actually constructing his machines to convince readers of their reality, a necessity given his use of reductio ad absurdum. The proof is constructive in nature: Turing describes what could be a real, buildable machine. The only questionable element is the existence of machine D, which the proof ultimately shows to be impossible.
Turing begins the proof by asserting the existence of a "decision/determination" machine D. When given any S.D (a string of symbols A, C, D, L, R, N, and semicolon), D determines whether this S.D represents a "computing machine" that is either "circular" (and therefore "unsatisfactory u") or "circle-free" (and therefore "satisfactory s"). Turing offers no comment on how D works. For argument's sake, we suppose D first checks if the string is well-formed (i.e., an algorithm, not a scramble of symbols), discarding it if not, and then goes "circle-hunting," possibly using heuristics. These details are not important for the proof.
Turing then loosely describes the algorithm for a machine he calls H. H contains decision-machine D as a subroutine. H's algorithm is expressed in its table of instructions, or perhaps in its Standard Description on tape combined with the universal machine U; Turing does not specify which. In describing universal machine U, Turing showed that a machine's S.D (a string of letters like a "program") can be converted to an integer in base 8, and vice versa. Any number N in base 8 can be converted to an S.D by replacing 1 with A, 2 with C, 3 with D, 4 with L, 5 with R, 6 with N, and 7 with semicolon. Machine H's unique number (D.N) is called "K." K is presumably a very long number, perhaps tens of thousands of digits, but this is unimportant.
Machine H converts any number N into an equivalent S.D symbol string for sub-machine D to test. In programming terms, H passes an arbitrary S.D to D, and D returns "satisfactory" or "unsatisfactory." H also keeps a tally R (perhaps "Record") of successful numbers; the number of successful S.D.s (R) is much smaller than the number tested (N). Finally, H prints a diagonal number called "beta-primed" B' on a section of its tape. H creates B' by simulating the motions of each satisfactory machine or number; eventually, the machine under test reaches its Rth figure (1 or 0), and H prints it. H then cleans up after the simulation, increments N, and continues testing indefinitely. All these machines that H hunts for are what the proof concerns.
- title
- On Computable Numbers, with an Application to the Entscheidungsproblem
- field
- mathematical logic, computability theory
- known_for
- proving the Entscheidungsproblem has no solution
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 submitted on 12 November 1936 and first published in 1937.
- It was the second proof (after Church's theorem) of the negation of Hilbert's Entscheidungsproblem.
- Turing's own words: 'what I shall prove is quite different from the well-known results of Gödel'.
- The third proof concludes in only 64 words and symbols via reductio ad absurdum.
- Turing's first proof shows that no machine can decide whether an arbitrary machine is 'circle-free' (i.e., prints its number forever).
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.
Frequently Asked Questions
What is Turing's proof?
It is the result from Alan Turing's 1936 paper 'On Computable Numbers, with an Application to the Entscheidungsproblem,' showing that no single mechanical procedure can decide the truth or falsity of every mathematical statement. It stands as the second independent demonstration (following Church's theorem) that Hilbert's decision problem is unsolvable.
What does Turing's proof actually establish?
Turing proved that certain decision problems are undecidable: there is no universal algorithm that can correctly output 'yes' or 'no' for every possible instance of a given problem. In plain terms, some purely mathematical questions are forever beyond what any computation can settle.
How does Turing's proof relate to Church's theorem?
Church's 1936 result, built on lambda calculus, was the first proof that the Entscheidungsproblem has no general solution, and Turing arrived at the same conclusion independently and almost simultaneously. Turing's contribution, however, introduced the abstract-machine model that went on to become the standard formalization of computation in computer science.
Why is Turing's proof considered so important?
It not only closed a major open question in mathematical logic but also supplied the concrete 'Turing machine' model that still defines what 'computable' means today. In doing so, it drew a sharp boundary between what mechanical processes can and cannot accomplish, influencing both logic and engineering.
What is the Entscheidungsproblem that Turing's proof addresses?
It is the question Hilbert posed in 1928 asking whether a single mechanical procedure could, for any formal mathematical statement, determine whether that statement is provable within a given system. Both Turing's and Church's results answered in the negative, proving no such universal decider can exist.
More in Mathematical Logic And Computation 1-21
Spotted an error? Know more?
This is a living reference — every entry is fact-audited, and reader corrections feed straight into our audit queue. Suggest an edit · See this site's audit record