Turing's Proof - Summary of The First Proof

Summary of The First Proof

Turing created a thicket of abbreviations; see the glossary at the end of this for help.

Some key clarifications:

Turing's machine H is attempting to print a diagonal number of 0s and 1s

This diagonal number is created when H actually "simulates" each "successful" machine under evaluation and prints the R-th "figure" (1 or 0) of the R-th "successful" machine

• Turing spent much of his paper actually "constructing" his machines to convince us of their truth. This was required by his use of the reductio ad absurdum form of proof.
• We must emphasize the "constructive" nature of this proof. Turing describes what could be real machine, really buildable. The only questionable element is the existence of machine D, which this proof will eventually show to be impossible.

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".

Turing has previously demonstrated in his commentary that all "computing machines-- machines that compute a number as 1s and 0s forever-- can be written as an S.D on the tape of the “universal machine” U. Most of his work leading up to his first proof is spent demonstrating that a universal machine truly exists, i.e.

There truly exists a universal machine U

For each number N, there truly exists a unique S.D,

Every Turing machine has an S.D

Every S.D on U’s tape can be “run” by U and will produce the same “output” (figures 1, 0) as the original machine.

Turing makes no comment about how machine D goes about its work. For sake of argument, we suppose that D would first look to see if the string of symbols is "well-formed" (i.e. in the form of an algorithm and not just a scramble of symbols), and if not then discard it. Then it would go “circle-hunting”. To do this perhaps it would use “heuristics” (tricks: taught or learned). For purposes of the proof, these details are not important.

Turing then describes (rather loosely) the algorithm (method) to be followed by a machine he calls H. Machine H contains within it the decision-machine D (thus D is a “subroutine” of H). Machine H’s algorithm is expressed in H’s table of instructions, or perhaps in H’s Standard Description on tape and united with the universal machine U; Turing does not specify this.

In the course of describing universal machine U, Turing has demonstrated that a machine’s S.D (string of letters similar to a “program”) can be converted to an integer (base 8) and visa versa. Any number N (in base 8) can be converted to an S.D with the following replacements: 1 by A, 2 by C, 3 by D, 4 by L, 5 by R, 6 by N, 7 by semicolon ";".

As it turns out, machine H's unique number (D.N) is the number "K". We can infer that K is some hugely long number, maybe tens-of-thousands of digits long. 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. (In programming parlance: H passes an arbitrary "S.D” to D, and D returns “satisfactory” or “unsatisfactory”.) Machine H is also responsible for keeping a tally R (“Record”?) of successful numbers (we suppose that the number of "successful S.D's i.e. R is much less than the number of S.D's tested, i.e. N). Finally, H prints on a section of its tape a diagonal number “beta-primed” B’. 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.

Note: All these machines that H is hunting for are what Turing called "computing machines". These compute binary-decimal-numbers in an endless stream of what Turing called "figures": only the symbols 1 and 0.

An example: Suppose machine H has tested 13472 numbers and produced 5 satisfactory numbers, i.e. H has converted the numbers 1 through 13472 into S.D’s (symbol strings) and passed them to D for test. As a consequence H has tallied 15 satisfactory numbers and run the first one to its 1st “figure”, the second to its 2nd figure, the third to its 3rd figure, the fourth to its 4th figure, and the fifth to its 5th figure. The count now stands at N = 13472, R = 5, and B’ = “.10011” (for example). H cleans up the mess on its tape, and proceeds:

H increments N = 13453 and converts "13453" to symbol string ADRLD. If sub-machine D deems ADLRD unsatisfactory, then H leaves the tally-record R at 5. H will increment the number N to 13454 and proceed onward. On the other hand, if D deems ADRLD satisfactory then H will increment R to 6. H will convert N (again) into ADLRD and “run” it using the universal machine U until this machine-under-test (U "running" ADRLD) prints its 6th “figure” i.e. 1 or 0. H will print this 6th number (e.g. “0”) in the “output” region of its tape (e.g. B’ = “.100110”).

H cleans up the mess, and then increments the number N to 13454.

The whole process unravels when H arrives at its own number K. We will proceed with our example. Suppose the successful-tally/record R stands at 12. H finally arrives at its own number minus 1, i.e. N = K-1 = 4335...3214, and this number is unsuccessful. Then H increments N to produce K = 4355...3215, i.e. its own number. H converts this to “LDDR...DCAR” and passes it to decision-machine D. Decision-machine D must return “satisfactory” (that is: H must by definition go on and on testing, ad infinitum, because it is "circle-free"). So ... H now increments tally R from 12 to 13 and then re-converts the number-under-test K into its S.D and uses U to simulate it. But this means that H will be simulating its own motions. (What's so wrong with thinking about your own thinking? Marvin Minsky makes the same point...) What is the first thing the simulation will do? This simulation K-aka-H either creates a new N or “resets” the “old” N to 1. This "K-aka-H" either creates a new R or “resets” the “old” R to 0. Old-H “runs” new "K-aka-H" until it arrives at its 12th figure.

But it never makes it to the 13th figure; K-aka-H eventually arrives at 4355...3215, again, and K-aka-H must repeat the test. K-aka-H will never reach the 13th figure. The H-machine probably just prints copies of itself ad infinitum across blank tape. 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. (We also will see the same thing if N is reset to 1 and R is reset to 0).

If the reader does not believe this, they can write a "stub" for decision-machine D (stub "D" will return "satisfactory") and then see for themselves what happens at the instant machine H encounters its own number.