It was the second proof (after Church's theorem) of the negation of Hilbert's Entscheidungsproblem; that is, the conjecture that some purely mathematical yes–no questions can never be answered by computation; more technically, that some decision problems are "undecidable" in the sense that there is no single algorithm that infallibly gives a correct "yes" or "no" answer to each instance of the problem.
As per UK copyright law, the novella entered the public domain on 1 January 2025, 70 full calendar years after Turing's death on 7 June 1954.
Turing begins the proof with the assertion of the existence of a “decision/determination” machine D. When fed any S.D (string of symbols A, C, D, L, R, N, semicolon “;”) it will determine if this S.D (symbol string) represents a "computing machine" that is either "circular" — and therefore "un-satisfactory u" — or "circle-free" — and therefore "satisfactory s".
But this is not important to what follows.Machine H is responsible for converting any number N into an equivalent S.D symbol string for sub-machine D to test.
H creates this B’ by “simulating” (in the computer-sense) the “motions” of each “satisfactory” machine/number; eventually this machine/number under test will arrive at its Rth “figure” (1 or 0), and H will print it.
H then is responsible for “cleaning up the mess” left by the simulation, incrementing N and proceeding onward with its tests, ad infinitum.
H cleans up the mess on its tape, and proceeds: H increments N = 13473 and converts "13473" to symbol string ADRLD.
But this contradicts the premise that H is a satisfactory, non-circular computing machine that goes on printing the diagonal numbers's 1's and 0's forever.
This is what Turing does: From M he creates a collection of machines {M1, M2, M3, M4, ..., Mn} and about each he writes a sentence: “X prints at least one 0” and allows only two “truth values”, True = blank or False = :0:.
One by one he determines the truth value of the sentence for each machine and makes a string of blanks or :0:, or some combination of these.
)Both Lemmas #1 and #2 are required to form the necessary "IF AND ONLY IF" (i.e. logical equivalence) required by the proof: A set E is computably decidable if and only if both E and its complement are computably enumerable (Franzén, p. 67)Turing demonstrates the existence of a formula Un(M) which says, in effect, that "in some complete configuration of M, 0 appears on the tape" (p. 146).
Readers should also come equipped with a solid background in (i) logic (ii) the paper of Kurt Gödel: "On Formally Undecidable Propositions of Principia Mathematica and Related Systems".
To follow the technical details, the reader will need to understand the definition of "provable" and be aware of important "clues".
"Provable" means, in the sense of Gödel, that (i) the axiom system itself is powerful enough to produce (express) the sentence "This sentence is provable", and (ii) that in any arbitrary "well-formed" proof the symbols lead by axioms, definitions, and substitution to the symbols of the conclusion.
To make things more confusing, Turing calls these symbols S0, S1, and S2, i.e. (iii) A "computing machine", whether it is built directly into a table (as his first examples show), or as machine-code M on universal-machine U's tape, prints its number on blank tape (to the right of M-code, if there is one) as 1s and 0s forever proceeding to the right.
(vi) Turing reduced the vast possible number of instructions in "M-code" (again: the code of M to appear on the tape) to a small canonical set, one of three similar to this: {qi Sj Sk R ql} e.g.
It is encoded as follows ; D A A A A A D C D L D A A ASecond clue: Turing is using ideas introduced in Gödel's paper, that is, the "Gödelization" of (at least part of) the formula for Un(M).
This clue appears only as a footnote on page 138 (Davis (1965), p. 138): "A sequence of r primes is denoted by ^(r)" (ibid.)
...)[6] Earlier in the paper Turing had previously used this expression (p. 138) and defined N(u) to mean "u is a non-negative integer" (ibid.)
But, with the Bernays corrections, Turing abandoned this approach (i.e. the use of N(u)) and the only place where "the Gödel number" appears explicitly is where he uses F^(n).
A theorem is any statement in the language of the system obtainable by a series of applications of the rules of reasoning, starting from the axioms.
In the following, we have to remind ourselves that every one of Turing's “computing machines” is a binary-number generator/creator that begins work on “blank tape”.
In the cases of R, L, E, P0, and P1 after doing its task the machine continues on to the next instruction in numerical sequence; ditto for the jumps if their tests fail.
(b)110 J0_7 (b)110 H Here at the end we find that a blank on the left has “come into play” so we leave it as part of the total configuration.
And even after Bernays' suggestions and Turing's corrections, errors remained in the description of the universal machine.
Hodges p. 125) — mainly because he had arrived simultaneously at a similar reduction of "algorithm" to primitive machine-like actions, so he took a personal interest in the proof.
Strangely (perhaps World War II intervened) it took Post some ten years to dissect it in the Appendix to his paper Recursive Unsolvability of a Problem of Thue, 1947.
[d] Other problems present themselves: In his Appendix Post commented indirectly on the paper's difficulty and directly on its "outline nature"[e] and "intuitive form" of the proofs.
[f] Anyone who has ever tried to read the paper will understand Hodges' complaint: The paper started attractively, but soon plunged (in typical Turing manner) into a thicket of obscure German Gothic type in order to develop his instruction table for the universal machine.
For example, the operations in the first line are PSk = PRINT symbol Sk from the collection A, C, D, 0, 1, u, v, w, x, y, z, :, then move tape LEFT.