Turing's proof
Glossary of terms used by Turing

1 computable number — a number whose decimal is computable by a machine (i.e., by finite means such as an algorithm)

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.

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 β’ —“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

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.

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.

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 (S.D) 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".
change_case:english_capital, keywords:letter_frequency