Turing's proof

Turing's proof is a proof by Alan Turing, first published in January 1937 with the title "On Computable Numbers, With an Application to the Entscheidungsproblem." It was the second proof of the assertion (Alonzo Church's proof was first) that some decision problems are "undecidable": there is no single algorithm that infallibly gives a correct "yes" or "no" answer to each instance of the problem. In his own words: "...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]..." (Undecidable, p. 145).

Turing preceded this proof with two others. The second and third both rely on the first. All rely on his development of type-writer-like "computing machines" that obey a simple set of rules and his subsequent development of a "universal computing machine".

Richard's paradox

In 1905, Jules Richard presented this profound paradox. Alan Turing's first proof constructs this paradox with his so-called computing machine and proves that this machine cannot answer a simple question: will this machine be able to determine if any computing machine (including itself) will become trapped in an unproductive "infinite loop" (i.e. it fails to continue its computation of the diagonal number).

A succinct definition of Richard's paradox is found in Whitehead and Russell's Principia Mathematica:

Richard's paradox... is as follows. Consider all decimals that can be defined by means of a finite number of words; let E be the class of such decimals. Then E has [aleph-sub-zero — an infinity of] terms; hence its members can be ordered as the 1st, 2nd, 3rd, ... Let N be a number defined as follows [Whitehead & Russell now employ the Cantor diagonal method]; if the nth figure in the nth decimal is p, let the nth figure in N be p+1 (or 0, if p = 9). Then N is different from all the members of E, since, whatever finite value n may have, the nth figure in N is different from the nth figure in the nth of the decimals composing E, and therefore N is different from the nth decimal. Nevertheless we have defined N in a finite number of words [i.e. this very word-definition just above!] and therefore N ought to be a member of E. Thus N both is and is not a member of E (Principia Mathematica, 2nd edition 1927, p. 61).

Complications

Turing's proof is complicated by a large number of definitions, and confounded with what Martin Davis called "petty technical details" and "...technical details [that] are incorrect as given" (Davis's commentary in Undecidable, p. 115). Turing himself published "A correction" in 1937: "The author is indebted to P. Bernays for pointing out these errors" (Undecidable, p. 152).

Specifically, in its original form the third proof is badly marred by technical errors. And even after Bernays' suggestions and Turing's corrections, errors remained in the description of the universal machine. And confusingly, since Turing was unable to correct his original paper, some text within the body harks to Turing's flawed first effort.

Bernays' corrections may be found in The Undecidable, pp. 152–154; the original is to be found as:

"On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction," Proceedings of the London Mathematical Society (2), 43 (1936–37), 544-546.

The on-line version of Turing's paper has these corrections in an addendum; however, corrections to the Universal Machine must be found in an analysis provided by Emil Post.

At first, the only mathematician to pay close attention to the details of the proof was Post (cf. 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 (reprinted in Undecidable, p. 293).

Before readers tackle "Proof #3" they are adivsed to place those corrections on their copy of the proof.

Other problems present themselves: In his Appendix Post commented indirectly on the paper's difficulty and directly on its "outline nature" (Post in Undecidable, p. 299) and "intuitive form" of the proofs (ibid.). Post had to infer various points:

"If our critique is correct, a machine is said to be circle-free if it is a Turing computing ... machine which prints an infinite number of 0s and 1s. And the two theorems of Turing's in question are really the following. There is no Turing ... machine which, when supplied with an arbitrary positive integer n, will determine whether n is the D.N of a Turing computing ... machine that is circle-free. [Secondly], There is no Turing convention-machine which, when supplied with an arbitrary positive integer n, will determine whether n is the D.N of a Turing computing ... machine that ever prints a given symbol (0 say)" (Post in Undecidable, p. 300)

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. The last people to give it a glance would be the applied mathematicians who had to resort to practical computation..." (Hodges p. 124)

Summary of the proofs

In his proof that the Entscheidungsproblem can have no solution, Turing proceeded from two proofs that were to lead to his final proof. His first theorem is most relevant to the halting problem, the second is more relevant to Rice's theorem.

First proof: that no "computing machine" exists that can decide whether or not an arbitrary "computing machine" (as represented by an integer 1, 2, 3, . . .) is "circle-free" (i.e. goes on printing its number in binary ad infinitum): "...we have no general process for doing this in a finite number of steps" (p. 132, ibid.). Turing's proof, although it seems to use the "diagonal process", in fact shows that his machine (called H) cannot calculate its own number, let alone the entire diagonal number (Cantor's diagonal argument): "The fallacy in the argument lies in the assumption that B [the diagonal number] is computable" (Undecidable, p. 132). The proof does not require much mathematics.

Second proof: This one is perhaps 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)" (his italics, Undecidable, p. 134).

Third proof: "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" (Undecidable, p. 145)

[Readers who brave Proof #3 should 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 (reprinted in Undecidable, p. 5). For assistance with Gödel's paper they should consult e.g. Ernest Nagel and James R. Newman, Godel’s Proof, New York University Press, 1958.]

This proof requires the use of formal logic to prove a first lemma, followed by a brief word-proof of the second:

"Lemma 1: If S1 [symbol "0"] appears on the tape in some complete configuration of M, then Un(M) is provable" (Undecidable, p. 147)
"Lemma 2: [The converse] If Un(M) is provable then S1 [symbol "0"] appears on the tape in some complete configuration of M" (Undecidable, p. 148)

Finally, in only 64 words and symbols Turing proves by reductio ad absurdum that "the Hilbert Entscheidungsproblem can have no solution" (Undecidable, p. 145).

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 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 5 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 = 13473 and converts "13473" 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 13474 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 [this is just an example, ADLRD is probably useless] 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 13474.

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

Summary of the second proof

Less than one page long, the passage from premises to conclusion is obscure.

Turing proceeds by reductio ad absurdum. He asserts the existence of a machine E, which when given the S.D (standard description, i.e. "program") of an arbitrary machine M, will determine whether M ever prints a given symbol (0 say). He does not assert that this M is a "computing machine".

Given the existence of machine E, Turing proceeds as follows:

  1. If machine E exists then a machine G exists that determines if M prints 0 infinitely often, AND
  2. If E exists then another process exits [we can call the process/machine G' for reference] that determines if M prints 1 infinitely often, THEREFORE
  3. When we combine G with G' we have a process that determines if M prints an infinity of figures, AND
  4. IF the process "G with G'" determines M prints an infinity of figures, THEN "G with G'" has determined that M is circle-free, BUT
  5. This process "G with G'" that determine if M is circle-free, by proof 1, cannot exist, THEREFORE
  6. Machine E does not exist.

Details of second proof

The difficulty in the proof is step 1. The reader will helped by realizing that Turing is not explaining his subtle handiwork. (In a nutshell: he is using certain equivalencies between the “existential-“ and “universal-operators” together with their equivalent expressions written with logical operators.)

Here’s an example: Suppose we see before us a parking lot full of hundreds of cars. We decide to go around the entire lot looking for: “Cars with flat (bad) tires”. After an hour or so we have found two “cars with bad tires.” We can now say with certainty that “Some cars have bad tires”. Or we could say: “It’s not true that ‘All the cars have good tires’”. Or: “It is true that: ‘not all the cars have good tires”. Let us go to another lot. Here we discover that “All the cars have good tires.” We might say, “There’s not a single instance of a car having a bad tire.” Thus we see that, if we can say something about each car separately then we can say something about ALL of them collectively.

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. We might get something like this: “M1 prints a 0” = True AND “M2 prints a 0” = True AND “M3 prints a 0” = True AND “M4 prints a 0” = False, ... AND “Mn prints a 0” = False. He gets the string

BBB:0::0::0: ... :0: ... ad infinitum

if there are an infinite number of machines Mn. If on the other hand if every machine had produced a "True" then the expression on the tape would be

BBBBB....BBBB ... ad infinitum

Thus Turing has converted statements about each machine considered separately into a single "statement" (string) about all of them. Given the machine (he calls it G) that created this expression, he can test it with his machine E and determine if it ever produces a 0. In our first example above we see that indeed it does, so we know that not all the M's in our sequence print 0s. But the second example shows that, since the string is blanks then every Mn in our sequence has produced a 0.

All that remains for Turing to do is create a process to create the sequence of Mn's from a single M.

Suppose M prints this pattern:

M => ...AB01AB0010AB…

Turing creates another machine F that takes M and crunches out a sequence of Mn’s that successively convert the first n 0’s to “0-bar” (0):

M1 = ...AB01AB0010AB...
M2 = ...AB01AB0010AB...
M3 = ...AB01AB0010AB...
M4 = ...AB01AB0010AB...

He claims, without showing details, that this machine F is truly build-able. We can see that one of a couple things could happen. F may run out of machines that have 0’s, or it may have to go on ad infinitum creating machines to “cancel the zeros”.

Turing now combines machines E and F into a composite machine G. G starts with the original M, then uses F to create all the successor-machines M1, M2,. . ., Mn. Then G uses E to test each machine starting with M. If E detects that a machine never prints a zero, G prints :0: for that machine. If E detects that a machine does print a 0 (we assume, Turing doesn’t say) then G prints :: or just skips this entry, leaving the squares blank. We can see that a couple things can happen.

G will print no 0’s, ever, if all the Mn’s print 0’s, OR,
G will print ad infinitum 0’s if all the M’s print no 0’s, OR,
G will print 0’s for a while and then stop.

Now, what happens when we apply E to G itself?

If E(G) determines that G never prints a 0 then we know that all the Mn’s have printed 0’s. And this means that, because all the Mn came from M, that M itself prints 0’s ad infinitum, OR
If E(G) determines that G does print a 0 then we know that not all the Mn’s print 0’s; therefore M does not print 0’s ad infinitum.

As we can apply the same process for determining if M prints 1 infinitely often. When we combine these processes, we can determine that M does, or does not, go on printing 1’s and 0’s ad infinitum. Thus we have a method for determining if M is circle-free. By Proof 1 this is impossible. So the first assertion that E exists, is wrong: E does not exist.

Summary of the third proof

Here Turing proves "that the Hilbert Entscheidungsproblem can have no solution" (Undecidable, p. 145). Here he

“…show(s) that there can be no general process for determining whether a given formula U of the functional calculus K is provable.” (ibid.)
"A set E is computably decidable if and only if both E and its complement are computably enumerable" (Frankél, p. 67)
Summary of the proof

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). This formula is TRUE, that is, it is "constructible", and he shows how to go about this.

Then Turing proves two Lemmas, the first requiring all the hard work. (The second is the converse of the first.) Then he uses reductio ad absurdum to prove his final result:

  1. There exists a formula Un(M). This formula is TRUE, AND
  2. If the Entscheidungsproblem can be solved THEN a mechanical process exists for determining whether Un(M) is provable (derivable), AND
  3. By Lemmas 1 and 2: Un(M) is provable IF AND ONLY IF 0 appears in some "complete configuration" of M, AND
  4. IF 0 appears in some "complete configuration" of M THEN a mechanical process exists that will determine whether arbitrary M ever prints 0, AND
  5. By Proof 2 no mechanical process exists that will determine whether arbitrary M ever prints 0, THEREFORE
  6. Un(M) is not provable (it is TRUE, but not provable) which means that the Entscheidungsproblem is unsolvable.
Discussion of the third proof

If readers intend to study the proof in detail they should correct their copies of the pages of the third proof with the corrections that Turing supplied.

To (even attempt 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.

First clue: "Let us put the description of M into the first standard form of §6". Section 6 describes the very specific "encoding" of machine M on the tape of a "universal machine" U. This requires the reader to know some idiosyncrasies of Turing's universal machine U and the encoding scheme.

(i) The universal machine is a set of "universal" instructions that reside in an "instruction table". Separate from this, on U's tape, a "computing machine" M will reside as "M-code". The universal table of instructions can print on the tape the symbols A, C, D, 0, 1, u, v, w, x, y, z, : . The various machines M can print these symbols only indirectly by commanding U to print them.

(ii) The "machine code" of M consists of only a few letters and the semicolon, i.e. D, C, A, R, L, N, ; . Nowhere within the "code" of M will the numerical "figures" (symbols) 1 and 0 ever appear. If M wants U to print a symbol from the collection blank, 0, 1 then it uses one of the following codes to tell U to print them. To make things more confusing, Turing calls these symbols S0, S1, and S2, i.e.

blank = S0 = D
0 = S1 = DC
1 = S2 = DCC

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

(iv) If a "computing machine" is U+"M-code", then "M-code" appears first on the tape; the tape has a left end and the "M-code" starts there and proceeds to the right on alternate squares. When the M-code comes to an end (and it must, because of the assumption that these M-codes are finite algorithms), the "figures" will begin as 1s and 0s on alternate squares, proceeding to the right forever. Turing uses the (blank) alternate squares (called "E"- "eraseable"- squares) to help U+"M-code" keep track of where the calculations are, both in the M-code and in the "figures" that the machine is printing.

(v) A "complete configuration" is a printing of all symbols on the tape, including M-code [?] and "figures" up to that point, together with the figure currently being scanned (with a pointer-character printed to the left of the scanned symbol ?). If we have interpreted Turing's meaning correctly, this will be a hugely long set of symbols. But whether the entire M-code must be repeated is unclear; only a printing of the current M-code instruction is necessary plus the printing of all figures with a figure-marker).

(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. If machine is executing instruction #qi and symbol Sj is on the square being scanned, then Print symbol Sk and go Right and then go to instruction ql: The other instructions are similar, encoding for "Left" L and "No motion" N. It is this set that is encoded by the string of symbols qi = DA...A, Sj = DC...C, Sk = DC...C, R, ql = DA....A. Each instruction is separated from another one by the semicolon. For example, {q5, S1 S0 L q3} means: Instruction #5: If scanned symbol is 0 then print blank, go Left, then go to instruction #3. It is encoded as follows

; D A A A A A D C D L D A A A

Second 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 (Undecidable): "A sequence of r primes is denoted by ^(r)" (ibid.) [Here, r inside parentheses is "raised".] This "sequence of primes" appears in a formula called F^(n).

Third clue: This reinforces the second clue. Turing's original attempt at the proof uses the expression

(Eu)N(u) & (x)( ... etc. ...) (Undecidable, p. 146)

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.) (i.e. a Gödel number). 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).

What does this mean for the proof? The first clue means that a simple examination of the M-code on the tape will not reveal if a symbol 0 is ever printed by U+"M-code". A testing-machine might look for the appearance of DC in one of the strings of symbols that represent an instruction. But will this instruction ever be "executed?" Something has to "run the code" to find out. This something can be a machine, or it can be lines in a formal proof, i.e. Lemma #1.

The second and third clues mean that, as its foundation is Gödel's paper, the proof is difficult.

Details of the third proof


"A set E is computably decidable if and only if both E and its complement are computably enumerable" (Frankél, p. 67)
"A sentence A is said to be decidable in a formal system S if either A or its negation is provable in S" (Frankél, p. 65)

Frankel has defined "provable" earlier in his book:

"A formal system is a system of axioms (expressed in some formally defined language) and rules of reasoning (also called inference rules), used to derive the theorems of the system. 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. A proof is a finite sequence of such applications, leading to a theorem as its conclusion" (ibid p. 17).

Thus a "sentence" is a string of symbols, and a theorem is a string of strings of symbols.

Turing is confronted with the following tasks:

Thus the "string of sentences" will be strings of strings of symbols. The only allowed individual symbols will come from Godel's symbols defined in his paper.(In the following example we use the "<" and ">" around a "figure" to indicate that the "figure" is the symbol being scanned by the machine).

An example of what "complete configuration" means

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”. Properly constructed, it always cranks away ad infinitum, but its instructions are always finite. In Turing’s proofs, Turing’s tape had a “left end” but extended right ad infinitum. For sake of example below we will assume that the “machine” is not a Universal machine, but rather the simpler “dedicated machine” with the instructions in the Table.

Our example is based on a modified Post-Turing machine model of a Turing Machine. This model prints only the symbols 0 and 1. The blank tape is considered to be all b’s. Our modified model requires us to add two more instructions to the 7 Post-Turing instructions. The abbreviations that we will use are:

R, RIGHT: look to the right and move tape to left, or move tape head right
L, LEFT : look to the left and to move tape right, or move tape head left
E, ERASE scanned square (e.g. make square blank)
P0,: PRINT 0 in scanned square
P1,: PRINT 1 in scanned square
Jb_n, JUMP-IF-blank-to-instruction_#n,
J0_n, JUMP-IF-0-to-instruction_#n,
J1_n, JUMP-IF-1-to-instrucntion_#n,
HALT.

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.

But, for brevity, our examples will only use three squares. And these will always start as there blanks with the scanned square on the left: i.e. bbb. With two symbols 1, 0 and blank we can have 27 distinct configurations:

bbb, bb0, bb1, b0b, b00, b01, b1b, b10, b11, 0bb, 0b0, 0b1, 00b, 000, 001, 01b, 010, 011, 1bb, 1b0, 1b1, 10b, 100, 101, 11b, 110, 111

We must be careful here, because it is quite possible that an algorithm will (temporarily) leave blanks in between figures, then come back and fill something in. More likely, an algorithm may do this intentionally. In fact, Turing’s machine does this—it prints on alternate squares, leaving blanks between figures so it can print locator symbols.

Turing always left alternate squares blank so his machine could place a symbol to the left of a figure (or a letter if the machine is the universal machine and the scanned square is actually in the “program”). In our little example we will forego this and just put symbols ( ) around the scanned symbol, as follows:

b(b)0 this means, “Tape is blanks-to-the-left of left blank but left blank is “in play”, the scanned-square-is-blank, “0”, blanks-to-right”
1(0)1 this means, “Tape is blanks-to-the-left, then 1, scanned square is “0”

Let us write a simple program:

start: P1, R, P1, R, P1, H

Remember that we always start with blank tape. The complete configuration prints the symbols on the tape followed by the next instruction:

start config: (b) P1,
config #1: (1) R,
config #2: 1(b) P1,
config #3: 1(1) R,
config #4: 11(b) P1,
config #5: 11(1) H

Let us add “jump” into the formula. When we do this we discover why the complete configuration must include the tape symbols. (Actually, we see this better, below.) This little program prints three “1”s to the right, reverses direction and moves left printing 0’s until it hits a blank. We will print all the symbols that our machine uses:

start: P1, R, P1, R, P1, P0, L, J1_7, H
(b)bb P1,
(1)bb R,
1(b)b P1,
1(1)b R,
11(b) P1,
11(1) P0,
11(0) L,
1(1)0 J1_7
1(1)0 L
(1)10 J0_7
(1)10 L
(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.

Given that we have done our job correctly, we add the starting conditions and see “where the theorem goes”. The resulting configuration—the number 110—is the PROOF.

Glossary of terms used by Turing

1 computable number — a number whose decimal is computable by a machine, i.e. by finite means (e.g. an algorithm) [Turing Thesis]

2 M — a machine with a finite instruction table and a scanning/printing head. M moves an infinite tape divided into squares each “capable of bearing a symbol”. The machine-instructions are only the following: move one square left, move one square right, on the scanned square print symbol p, erase the scanned square, if the symbol is p then do instruction aaa, if the scanned symbol is not p then do instruction aaa, if the scanned symbol is none then do instruction aaa, if the scanned symbol is any do instruction aaa [where “aaa” is an instruction-identifier].

3 computing machine — an M that prints two kinds of symbols, symbols of the first type are called “figures” and are only binary symbols 1 and 0; symbols of the second type are any other symbols.

4 figures — symbols 1 and 0, a.k.a. “symbols of the first kind”

5 m-configuration — the instruction-identifier, either a symbol in the instruction table, or a string of symbols representing the instruction- number on the tape of the universal machine (e.g. "DAAAAA = #5")

6 symbols of the second kind — any symbols other than 1 and 0

7 circular — an unsuccessful computating machine. It fails to print, ad infinitum, the figures 0 or 1 that represent in binary the number it computes

8 circle-free — a successful computating machine. It prints, ad infinitum, the figures 0 or 1 that represent in binary the number it computes

9 sequence — as in “sequence computed by the machine”: symbols of the first kind a.k.a. figures a.k.a. symbols 0 and 1.

10 computable sequence — can be computed by a circle-free machine

11 S.D – Standard Description: a sequence of symbols A, C, D, L, R, N, “;” on a Turing machine tape

12 D.N — Description Number: an S.D converted to a number: 1=A, 2=C, 3 =D, 4=L, 5=R, 6=N, 7=;

13 M(n) — a machine whose D.N is number “n”

14 satisfactory — a S.D or D.N that represents a circle-free machine

15 U — a machine equipped with a “universal” table of instructions. If U is “supplied with a tape on the beginning of which is written the S.D of some computing machine M, U will compute the same sequence as M.”

16 B’—“beta-primed”: A so-called “diagonal number” made up of the n-th figure (i.e. 0 or 1) of the n-th computable sequence [also: the computable number of H, see below]

17 u — an unsatisfactory, i.e. circular, S.D

18 s — satisfactory, i.e. circle-free S.D

19 D — a machine contained in H (see below). When supplied with the S.D of any computing machine M, D will test M’s S.D and if circular mark it with “u” and if circle-free mark it with “s”

20 H — a computing machine. H computes B’, maintains R and N. H contains D and U and an unspecified machine (or process) that maintains N and R and provides D with the equivalent S.D of N. E also computes the figures of B’ and assembles the figures of B’.

21 R — a record, or tally, of the quantity of successful (circle-free) S.D tested by D

22 N — a number, starting with 1, to be converted into an S.D by machine E. E maintains N.

23 K — a number. The D.N of H.

Required for Proof #3

5 m-configuration — the instruction-identifier, either a symbol in the instruction table, or a string of symbols representing the instruction's number on the tape of the universal machine (e.g. "DAAAAA = instruction #5"). In Turing's S.D the m-configuration appears twice in each instruction, the left-most string is the "current instruction"; the right-most string is the next instruction.

24 complete configuration — the number (figure 1 or 0) of the scanned square, the complete sequence of all symbols on the tape, and the m-configuration (the instruction-identifier, either a symbol or a string of symbols representing a number, e.g. "instruction DAAAA = #5")

25 RSi(x, y) — "in the complete configuration x of M the symbol on square y is Si. "complete configuration" is definition #5,

26 I(x, y) — "in the complete configuration x of M the square y is scanned"

27 Kqm(x) — "in the complete configuration x of M the machine-configuration (instruction number) is qm"

28 F(x,y) — "y is the immediate successor of x" (follows Gödel's use of "f" as the successor-function).

29 G(x,y) — "x precedes y", not necessarily immediately

30 Inst{qi, Sj Sk L ql} is an abbreviation, as are Inst{qi, Sj Sk R ql}, and Inst{qi, Sj Sk N ql}. See below.

Turing reduces his instruction set to three “canonical forms” – one for Left, Right, and No-movement. Si and Sk are symbols on the tape.

tape Final
m-config Symbol Operations m-config
qi Si PSk, L qm
qi Si PSk, R qm
qi Si PSk, N qm

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.

These he further abbreviated as: (N1) qi Sj Sk L qm (N2) qi Sj Sk R qm (N3) qi Sj Sk N qm

In Proof #3 he calls the first of these “Inst{qi Sj Sk L ql}”, and he shows how to write the entire machine S.D as the logical conjunction (logical OR): this string is called “Des(M)”, as in “Description-of-M”. i.e. if the machine prints 0 then 1’s and 0’s on alternate squares to the right ad infinitum it might have the table (a similar example appears on page 119):

q1, blank, P0, R, q2
q2, blank, P-blank, R, q3
q3, blank, P1, R, q4
q4, blank, P-blank, R, q1

(This has been reduced to canonical form with the “p-blank” instructions so it differs a bit from Turing’s example.) If put them into the “ Inst( ) form” the instructions will be the following (remembering: S0 is blank, S1 = 0, S2 = 1):

Inst {q1 S0 S1 R q2}
Inst {q2 S0 S0 R q3}
Inst {q3 S0 S2 R q4}
Inst {q4 S0 S0 R q1}

The reduction to the Standard Description SD will be:

;D A D D C R D A A; D A A D D R D A A A ; D A A A D D C C R D A A A A ; D A A A A D D R D A ;

This agrees with his example in the book (there will be a blank between each letter and number). Universal machine U uses the alternate blank squares as places to put "pointers".

References

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.