4. Abbreviated tables
There are certain types of process used by nearly all machines, and these, in some machines, are used in many connections. These processes include copying down sequences of symbols, comparing sequences, erasing all symbols of a given form, etc. Where such processes are concerned we can abbreviate the tables for the m-configurations considerably by the use of “skeleton tables”. In skeleton tables there appear capital German letters [4] and small Greek letters. These are of the nature of “variables”. By replacing each capital German letter throughout by an m-configuration {236} and each small Greek letter by a symbol, we obtain the table for an m-configuration.
The skeleton tables are to be regarded as nothing but abbreviations: they are not essential. So long as the reader understands how to obtain the complete tables from the skeleton tables, there is no need to give any exact definitions in this connection.
Let us consider an example:
m-configuration |
Symbol |
Behaviour |
Final m-config. |
|
f(C, B, α) |
{ |
ə
not ə |
L
L |
f1(C, B, α)
f(C, B, α) |
From the m-configuration f(C, B, α) the machine finds the symbol of form α which is farthest to the left (the “first α”) and the m-configuration then becomes C. If there is no α then the m-configuration becomes B. |
f1(C, B, α) |
{ |
α
not α
None |
R
R |
C
f1(C, B, α)
f2(C, B, α) |
f2(C, B, α) |
{ |
α
not α
None |
R
R |
C
f1(C, B, α)
B |
If we were to replace C throughout by q (say), B by r, and α by x, we should have a complete table for the m-configuration f(q , r, x). f is called an “m-configuration function” or “m-function”.
The only expressions which are admissible for substitution in an m-function are the m-configurations and symbols of the machine. Those have to be enumerated more or less explicitly: they may include expressions such as p (e, x); indeed they must if there are any m-functions used at all. If we did not insist on this explicit enumeration but simply stated that the machine had certain m-configurations (enumerated) and all m-configurations obtainable by substitution of m-configurations in certain m-functions, we should usually get an infinity of m-configurations; e.g., we might say that the machine was to have the m-configuration q and all m-configurations obtainable by substituting an m-configuration for C in p(C). Then it would have q, p(q), p(p(q)), p(p(p(q))), ... as m-configurations.
Our interpretation rule then is this. We are given the names of the m-configurations of the machine, mostly expressed in terms of m-functions. We are also given skeleton tables. All we want is the complete table for the m-configurations of the machine. This is obtained by repeated substitution in the skeleton tables.
{237} Further examples.
(In the explanations the symbol “→” is used to signify “the machine goes into the m-configuration ...”)
e(C, B, α) |
|
f(e1(C, B, α),B, α) |
From e(C, B, α) the first α is erased and →C. If there is no α →B. |
e1(C, B, α) |
E |
C |
e(B, α) |
|
e(e(B, α)S,B, α) |
From e(, α) all letters α are erased and →B. |
The last example seems somewhat more difficult to interpret than most. Let us suppose that in the list of m-configurations of some machine there appears e(b, x) (= q, say). The table is
e(b, x) |
|
e ( e(b, x), b, x) |
|
or |
q |
|
|
e,(q, b, x). |
|
|
Or, in greater detail: |
|
q |
|
|
e(q, b, x) |
|
e(q, b, x) |
|
|
f(e1(q, b, x), b, x |
|
e1(q, b, x) |
E |
q. |
|
|
In this we could replace e1(q, b, x) by q' and then give the table for f (with the right substitutions) and eventually reach a table in which no m-functions appeared. |
pe(C,β) |
|
|
f(pe1(C, β) C, e)
|
From pe(C,β) the machine prints β at the end of the sequence of symbols and →C. |
pe1(C, β) |
{ |
Any
None |
R, R
Pβ |
pe1(C,β)
C |
f(C)
r(C) |
|
|
L
R |
CC |
From f'(C, B, α) it does the same as for f(C, B, α) but moves to the left before →C. |
f'(C, B, α) |
|
|
|
f(l(C), B, α) |
|
f''(C, B, α) |
|
|
|
f(r(C), B, α) |
|
c(C, B, α)
c1(C) |
|
β |
|
f'(c1(C), B, α)
pe(C, β) |
c(C, B, α). The machine writes at the end the first symbol marked α and →C. |
{238} The last line stands for the totality of lines obtainable from it by replacing β by any symbol which may occur on the tape of the machine concerned.
ce(C, B, α)
ce(B, α) |
|
c(e(C, B, α),B, α)
ce(ce(B, α),B, α) |
ce(B, α)). The machine copies down in order at the end all symbols marked α and erases the letters α; →B. |
re ( C, B, α, β)
r e1 ( C, B, α,β) |
E,Pβ |
f(re1(C, B, α,β)B, α)
C |
re(C, B, α,β). The machine replaces the first α by β and →C→B if there is no α. |
re(B, α,β) |
|
re(re(B, α,β) B, α,β) |
'
re(B, α,β). The machine replaces all letters α byβ →B. |
er(C, B, α)
cr(C, B, α) |
|
c(re(C, B, α, α) B, α)
cr(re(B, α, α), α) |
cr(B, α) differs from ce(B, α) only in that the letters α are not erased. The m-configuration cr(B, α) is taken up when no letters “a” are on the tape. |
cr(C, U, B,α,β) |
|
f'(cp1(C1, U, B, β), α) |
cp1(C1, U, β) |
{ |
γ |
f'(cp2(C1, U, γ), U, β) |
cp2(C1, U, γ) |
γ
not γ |
C
U. |
The first symbol marked α and the first marked β are compared. If there is neither α nor β →E. If there are both and the symbols are alike, →C. Otherwise →U.
cpe(C, U, α, β) |
cpe(e(C, C, β), C, α), U, E, α, β) |
cpe(C, U, E, α, β) differs from cp(C, U, E, α, β) in that in the case when there is similarity the first α and β are erased.
cpe(U, E, α, β) |
cpe(cpe(U, E, α, β ),U, E, α, β). |
The sequence of symbols marked α is compared with the sequence marked β. →E if they are similar. Otherwise →U. Some of the symbols α and β are erased.
cpe(C, E, α, β) |
cp(e(cpe(U, E, α, β, C, α), U, E, α, β)***** |
cpe(U, E, α, β) differs from cp(U, E, α, β) in that the case where there is similarity to the first α and β are erased.
{239}
q(C) |
{ |
Any
None |
R
R |
q(C)
q1(C) |
q(C, α). The machine finds the last symbol of form α. →C. |
q1(C) |
{ |
Any
None |
R
|
q(C)
C |
|
q(C, α) |
|
|
|
q(q1(C, α)) |
q1(C, α) |
{ |
I
not α |
L |
C
q1(C, α) |
|
pe2(C, α, β) |
|
|
|
pe(pe(C, β), α) |
pe2(C, α, β). The machine prints α β at the end. |
ce2(B, α, β) |
|
|
|
ce(ce(B, β), α) |
ce3(B, β, α, γ). The machine copies down at the end first the symbols marked α, then those marked β, and finally those marked γ; it erases the symbols α, β, γ. |
ce3(B, β, γ, α) |
|
|
|
ce(ce2(B, β, γ), α) |
e(C) |
{ |
ə
Not ə |
R
L |
e1(C)
e(C) |
From e(C) the marks are erased from all marked symbols. →C. |
e1(C) |
{ |
Any
None |
R, E, R
|
e1(C)
C |
|
|
|
|
5. Enumeration of computable sequences.
A computable sequence γ is determined by a description of a machine which computes γ.
Thus the sequence 001011011101111... is determined by the table on p.234,
and, in fact, any computable sequence is capable of being described in
terms of such a table.
It will be useful to put these tables into a kind of standard form. In
the first place let us suppose that the table is given in the same form
as the first table, for example, I on p.233.
That is to say, that the entry in the operations column is always of one
of the forms E : E, R : E, L : Pα : Pα, R : Pα, L : R : L : or no entry at
all. The table can always be put into this form by introducing more m-configurations.
Now let us give numbers to the m-configurations, calling them q1, ..., qR,
as in § 1. The initial m-configuration
is always to be called q1. We also
give numbers to the symbols S1,
…, Sm {240} and,
in particular, blank = S0, 0 = S1, l = S2. The lines of the table
are now of form
m-config.
|
symbol
|
operations
|
final m-config.
|
|
q i
|
S j
|
PS k, L
|
q m
|
(N 1)
|
q i
|
S j
|
PS k, R
|
q m
|
(N 2)
|
q i
|
S j
|
PS k
|
q m
|
(N 3)
|
Lines such as
Are to be written as
And lines such as
To be written as
In this way we reduce each line of the table to a line of one of the
forms (N1), (N2),
(N3).
From each line of form ((N1) let
us form an expression qi S jSk R qm ;
from each line of form (N1) we form
an expression qi S jSk R qm ;
and from each line of form (N3)
we form an expression qi Sj Sk N qm .
Let us write down all expressions so formed from the table for the machine
and separate them by semi-colons. In this way we obtain a complete description
of the machine. In this description we shall replaceqiby the letter “D” followed by the letter “A”
repeated i times, and S j by “D” followed by “C” repeated
j times. This new description of the machine may be called
the standard description (S.D). It is made up entirely from the
letters “A”, “C”, “D”,
“L”, “R”, “N”,
and from “;”.
If finally we replace “A” by “1”, “C”
by “2”, “D” by “3”, “L”
by “4”, “R” by “5”, “N”
by “6”, and “;” by “7”
we shall have a description of the machine in the form of an arabic numeral.
The integer represented by this numeral may be called a description
number (D.N) of the machine. The D.N determine the S.D and the structure
of the {241} machine uniquely.
The machine whose D.N is n may be described as M (n).
To each computable sequence there corresponds at least one description
number, while to no description number does there correspond more than
one computable sequence. The computable sequences and numbers arc therefore
enumerable.
Let us find a description number for the machine I of §3. When we rename
the m-configurations its table becomes:
q1 |
S0 |
PS1 |
q2 |
q2 |
S0 |
PS0, R |
q3 |
q3 |
S0 |
PS2, R |
q4 |
q4 |
S0 |
PS0, R |
q1 |
Other tables could be obtained by adding irrelevant lines such as
Our first standard form would be
q1 S0 S1 Rq2 ; q2 S0 S0 Rq3 ; q3 S0 S2 Rq4 ;
q4 S0 S0 Rq1 ;.
The standard description is
DADDCRDAA; DAADDRDAAA; |
|
DAAADDCCRDAAAA; DAAAADDRDA; |
A description number is
31332531173113353111731113322531111731111335317
and so is
31332531173113353111731113322531L1173111133531731323253117
A number which is a description number of a circle-free machine will
be called a satisfactory number. In §8 it is shown that there can be no general process for determining whether
a given number is satisfactory or not. |
6. The universal computing machine.
It is possible to invent a single machine which can be used to compute
any computable sequence. If this machine U is supplied with a tape on the beginning of which is written the S.D of
some computing machine M , {242} then U will compute the same sequence as M .
In this section I explain in outline the behavior of the machine. The
next section is devoted to giving the complete table for U .
Let us first suppose that we have a machine M' which will write down on the F-squares the successive complete
configurations of M . These might be expressed
in the same form as on p.235, using the second description,
(C), with all symbols on one line. Or, better, we could transform this
description (as in §5) by replacing each m-configuration
by “D” followed by “A” repeated
the appropriate number of times, and by replacing each symbol by “D”
followed by “C” repeated the appropriate number of
times. The numbers of letters “A” and “C”
are to agree with the numbers chosen in §5, so
that, in particular, “0” is replaced by “DC”,
“1” by “DCC”, and the blanks by “D”
. These substitutions are to be made after the complete configurations
have been put together, as in (C). Difficulties arise if we do the substitution
first. In each complete configuration the blanks would all have to be
replaced by “D” , so that the complete configuration
would not be expressed as a finite sequence of symbols.
If in the description of the machine II of §3 we replace “o” by “DAA”, “ə”
by “DCCC ”, “q”by
“DAAA”, then the sequence (C) becomes:
DA : DCCCDCCCDAADCDDC : DCCCDCCCDAAADCDDC : ... (C1)
(This is the sequence of symbols on F-squares.)
It is not difficult to see that if M can
be constructed, then so can M '. The manner
of operation of M ' could be made to depend
on having the rules of operation (i.e., the S.D) of it written
somewhere within itself (i.e. within M ');
each step could be carried out by referring to these rules. We have only
to regard the rates as being capable of being taken out and exchanged
or others and we have something very akin to the universal machine.
One thing is lacking: at present the machine M '
prints no figures. We may correct this by printing between each successive
pair of complete configurations the figures which appear in the new configuration
but not in the old. Then (C1) becomes
DDA : 0 : 0 : DCCCDCCCDAADCDDC : DCCC.... (C2)
It is not altogether obvious that the E-squares leave enough
room for the necessary “rough work”, but this is, in fact,
the case.
The sequences of letters between the colons in expressions such as (C1)
may be used as standard descriptions of the complete configurations. When
the letters are replaced by figures, as in §5,
we shall have a numerical {243} description of the complete configuration, which may be called its description number. |
7. Detailed description of the universal machine.
A table is given below of the behaviour of this universal machine. The m-configurations of which the machine is capable are all those
occurring in the first and last columns of the table, together with all
those which occur when we write out the unabbreviated tables of those
which appear in the table in the form of m-functions. E.g., e(anf)
appears in the table and is an m-function. Its unabbreviated
table is (see p. 239)
e(anf) |
{ |
ə
not ə |
R
L |
e1(anf)
e(anf) |
e(anf) |
{ |
Any
None |
R, E, R
|
e1(anf)
e(anf) |
Consequently e1(anf) is an m-configuration of U .
When U is ready to start work the tape running
through it bears on it the symbol ə on an F-square and again ə on the next E-square; after this, on F-squares only, comes the S.D of
the machine followed by a double colon “: :”
(a single symbol, on an F-square). The S.D consists of a number
of instructions, separated by semi-colons.
Each instruction consists of five consecutive parts
i ) “ D ” followed by a sequence of letters “ A ”.
This describes the relevant m-configuration.
ii ) “ D ” followed by a sequence of letters “ C ”.
This describes the scanned symbol.
iii ) “ D ” followed by another sequence of letters
“ C ”. This describes the symbol into which the scanned
symbol is to be changed.
iv ) “ L ”, “ R ”, “ N ”,
describing whether the machine is to move to left, right, or not at all.
v ) “ D ” followed by a sequence of letters “ A ”.
This describes the final m-configuration.
The machine U is to be capable of printing
“ A ”, “ C ”, “ D ”,
“ 0 ”, “ 1 ”, “ u ”, “ v ”,
“ w ”, “ x ”, “ y ”,
“ z ”.
The S.D is formed from “ ; ”, “ A ”,
“ C ”, “ D ”, “ L ”,
“ R ”, “ N ”.
{244} Subsidiary skeleton table.
con(C, α) |
{ |
Not A
A |
R, R
L, Pα, R |
con(C, α)
con1(C, α) |
con(C, α).
Starting from an F-square, S say, the sequence C of symbols describing a configuration closest on the right of S is
marked out with letters α. →C. |
con1(C, α) |
{ |
A
D |
R, Pα, R
R, Pα, R |
con1(C, α)
con2(C, α) |
con2(C, α) |
{ |
C
Not C |
R, Pα, R
R, R |
con2(C, α)
C |
con(C, ).
In the final configuration the machine is scanning the square which
is four squares to the right of the last square of C. C is
left unmarked. |
The table for U.
b |
|
|
f(b1, b1, ::) |
b.
The machine prints :DA on the F-squares
after :: → anf. |
b1 |
R, R, P :, R, R, PD, R,
R, PA |
anf |
anf |
|
|
g(anf1, :) |
anf.
The machine marks the configuration in the last complete configuration
with y. → fom. |
anf1 |
|
|
con(fom, y) |
fom |
{ |
;
z
not z nor ; |
R, Pz, L
L, L
L |
con(fmp, x)
fom
fom |
fom. The machine finds
the last semi-colon not marked with z. It marks this semi-colon
with z and the configuration following it with x. |
fmp |
|
cpe(e(fom, x, y),sim, x, y) |
fmp. The machine compares
the sequences marked x and y. It erases all letters x and y. → sim if they
are alike. Otherwise → fom. |
anf. Taking the long view, the last instruction
relevant to the last configuration is found. It can be recognised afterwards
as the instruction following the last semi-colon marked z. → sim.
{245}
sim |
|
|
|
f'(sim1, sim1, z) |
sim.
The machine marks out the instructions. That part of the instructions
which refers to operations to be carried out is marked with u,
and the final m-configuration with y. The letters z are erased. |
sim1 |
|
|
|
con(sim2,
) |
sim2 |
{ |
A
Not A |
R, Pu, R, R, R |
sim3
sim2 |
sim3 |
{ |
Not A
A |
L, Py
L, Py, R, R, R |
e(mf, z)
sim3 |
mf |
|
|
|
g(mf, :) |
mf.
The last complete configuration is marked out into four sections.
The configuration is left unmarked. The symbol directly preceding
it is marked with x. The remainder of the complete configuration
is divided into two parts, of which the first is marked with v and the last with w. A colon is printed after the whole.n→ sh. |
mf1 |
{ |
Not A
A |
R, R
L, L, L, L |
mf1
mf2 |
mf2 |
{ |
C
:
D |
R, Px, L, L, L
R, Px, L, L, L |
mf2
mf4
mf3 |
mf3 |
{ |
not :
: |
R, Pv, L, L, L
|
mf3
mf4 |
mf4 |
|
|
|
con(l(l(mf5)), ) |
mf5 |
{ |
Any
None |
R, Pw, R
P: |
mf5
sh |
sh |
|
|
|
f(sh1, inst, u) |
sh.
The instructions (marked u) are examined. If it is found
that they involve “Print 0” or “Print 1”,
then 0: or 1: is printed at the
end. |
sh1 |
|
|
L, L, L |
sh2 |
sh2 |
{ |
D
not D |
R, R, R, R
|
sh2
inst |
sh3 |
{ |
C
not C |
R, R
|
sh4
inst |
sh4 |
{ |
C
not C |
R, R
|
sh5
pe2(inst,
0, :) |
sh5 |
{ |
C
not C |
|
inst
pe2(inst,
1, :) |
{246} |
|
inst |
|
|
g(l(inst1),u) |
inst.
The next complete configuration is written down, carrying out the
marked instructions. The letters u, v, w, x, y are erased. → anf. |
inst1 |
α |
R, E |
inst1(α) |
inst1(L) |
|
ce5(ov, v, y, x, u, w) |
inst1(R) |
|
ce5(ov, v, y, x, u, w) |
inst1(N) |
|
ce5(ov, v, y, x, u, w) |
|
ov |
|
e(anf) |
|
|
8. Application of the diagonal process.
It may be thought that arguments which prove that the real numbers are
not enumerable would also prove that the computable
numbers and sequences cannot be enumerable[5]. It might, for instance, be
thought that the limit of a sequence of computable numbers must be computable.
This is clearly only true if the sequence of computable numbers is defined
by some rule.
Or we might apply the diagonal process. “If the computable sequences
are enumerable, let αn be the n-th
computable sequence, and let φn (m) be the m-th figure in αn. Let β be the sequence with 1 – φn(n)
as its n-th figure. Since β is computable,
there exists a number K such that 1 – φn(n) = φK(n) all n. Putting n = K, we have 1 = 2φK(K), i.e. 1 is even. This is impossible. The computable sequences
are therefore not enumerable”.
The fallacy in this argument lies in the assumption that β is computable. It would be true if we could enumerate the computable
sequences by finite means, but the problem of enumerating computable sequences
is equivalent to the problem of finding out whether a given number is
the D.N of a circle-free machine, and we have no general process for doing
this in a finite number of steps. In fact, by applying the diagonal process
argument correctly, we can show that there cannot be any such general
process.
The simplest and most direct proof of this is by showing that, if this
general process exists, then there is a machine which computes β .
This proof, although perfectly sound, has the disadvantage that it may
leave the reader with a feeling that “there must be something wrong”.
The proof which I shall give has not this disadvantage, and gives a certain
insight into the significance of the idea “circle-free”. It
depends not on constructing β, but on constructing β', whose n-th
figure is φn(n).
{247} Let us suppose that there
is such a process; that is to say, that we can invent a machine D which, when supplied with the S.D of any computing machine M will test this S.D and if M is circular
will mark the S.D with the symbol “u” and if it is
circle-free will mark it with “s”. By combining the
machines D and U we could construct a machine M to compute
the sequence β'.
The machine D may require a tape. We may
suppose that it uses the E-squares beyond all symbols on F-
squares, and that when it has reached its verdict all the rough work done
by D is erased.
The machine H has its motion divided into
sections. In the first N –1 sections, among other things,
the integers 1, 2, …, N – 1 have been written down
and tested by the machine D. A certain number,
say R(N – 1), of them have been found to be the
D.N’s of circle-free machines. In the N-th section the
machine D tests the number N. If N is satisfactory, i.e., if it is the D.N of a circle-free
machine, then R(N) = 1 +R(N –
1) and the first R(N) figures of the sequence of which
a D.N is N are calculated. The R(N)-th figure
of this sequence is written down as one of the figures of the sequence β' computed
by H. If N is not satisfactory,
then R(N) = R(N – 1) and the
machine goes on to the (N + 1)-th section of its motion.
From the construction of H we can see that H is circle-free. Each section of the motion of H comes to an end after a finite number of steps. For, by our assumption
about D, the decision as to whether N is satisfactory is reached in a finite number of steps. If N is not satisfactory, then the N-th section is finished. If N is satisfactory, this means that the machine M(N)
whose D.N is N is circle-free, and therefore its R(N)-th
figure can be calculated in a finite number of steps. When this figure
has been calculated and written down as the R(N)-th
figure of β',
the N-th section is finished. Hence H is circle-free.
Now let K be the D.N of H. What
does H do in the K-th section of
its motion? It must test whether K is satisfactory, giving a
verdict “s” or “u”. Since K is the D.N of H and since H is circle-free, the verdict cannot be “u”. On the
other hand the verdict cannot be “s”. For if it were,
then in the K-th section of its motion H would be bound to compute the first R(K – 1)+1
= R(K) figures of the sequence computed by the machine
with K as its D.N and to write down the R(K)-th
as a figure of the sequence computed by H.
The computation of the first R(K) – 1 figures
would be carried out all right, but the instructions for calculating the R(K)-th would amount to “calculate the first R(K)
figures computed by H and write down the R(K)-th”.
This R(K)-th figure wonld never be found. I.e., H is circular, contrary both to what we have found in the last paragraph
and to the verdict “s”. Thus both verdicts are impossible
and we conclude that there can be no machine D.
{248} We can show further that there can be no machine R which, when
applied with the S.D of an arbitrary machine M,
will determine whetherM ever prints a given
symbol (0 say).
We will first show that, if there is a machine R,
then there is a general process for determining whether a given machine M prints 0 infinitely often. Let M1 be a machine which prints the same sequence as M,
except that in the position where the first 0 printed by M stands, M1 prints 0. M2 is to
have the first two symbols 0 replaced by 0,
and so on. Thus, if M were to print
A B A 01 A A B 0 0 1 0 A B…,
then M1 would print
A B A 0 1 A A B 0 0
1 0 A B…
and M2 would print
A B A 01 A A B 0 0 1 0 A B… .
Now let F be a machine which, when supplied
with the S.D of M, will write down successively
the S.D of M, of M1,
of M2, …
(there is such a machine). We combine F with R and obtain a new machine, G. In the motion
of G first F
is used to write down the S.D of M, and then R tests it, :0: is written if it is found
that M never prints 0; then F
writes the S.D of M1band this is tested, :0: being printed
if and only if M1 never prints 0; and so on. Now let us test G with R. If it is found that G never prints 0, then M prints 0 infinitely
often; if G prints 0 sometimes, then M does not print 0 infinitely often.
Similarly there is a general process for determining whether M prints 1 infinitely often. By a combination of these processes we have
a process for determining whether M prints
an infinity of figures, i.e. we have a process for determining
whether M is circle-free. There can therefore
be no machineR.
The expression “there is a general process
for determining …” has been need throughout this section as
equivalent to “there is a machine which will determine …”
This usage can be justified if and only if we can justify our definition
of “computable”. For each of these “general process”
problems can be expressed as a problem concerning a general process for
determining whether a given integer n has a property G(n)
[e.g. G(n) might mean “n is
satisfactory” or “ n is the Gödel representation of a provable formula”], and this is equivalent to
computing a number whose n-th figure is 1 if G (n)
is true and 0 if it is false. {249} |
9. The extent of the computable numbers.
No attempt has yet been made to show that the “computable”
numbers include all numbers which would naturally be regarded as computable.
All arguments which can be given are bound to be, fundamentally, appeals
to intuition, and for this reason rather unsatisfactory mathematically.
The real question at issue is “What are the possible processes which
can be carried out in computing a number?”
The arguments which I shall use are of three kinds.
- A direct appeal to intuition.
- A proof of the equivalence of two definitions (in case the new definition
has a greater intuitive appeal).
- Giving examples of large classes of numbers which are computable.
Once it is granted that computable numbers are all “computable”
several other propositions of the same character follow. In particular,
it follows that, if there is a general process for determining whether
a formula of the Hilbert function calculus is provable, then the determination
can be carried out by a machine.
I. [Type (a)]. This argument
is only an elaboration of the ideas of §1.
Computing is normally done by writing certain symbols on paper. We may
suppose this paper is divided into squares like a child's arithmetic book.
In elementary arithmetic the two-dimensional character of the paper is
sometimes used. But such a use is always avoidable, and I think that it
will be agreed that the two-dimensional character of paper is no essential
of computation. I assume then that the computation is carried out on one-dimensional
paper, i.e. on a tape divided into squares. I shall also suppose
that the number of symbols which may be printed is finite. If we were
to allow an infinity of symbols, then there would be symbols differing
to an arbitrarily small extent.[6] The effect of this
restriction of the number of symbols is not very serious. It is always
possible to use sequences of symbols in the place of single symbols. Thus
an Arabic numeral such as {250} 17 or 999999999999999 is normally treated as a single symbol. Similarly
in any European language words are treated as single symbols (Chinese,
however, attempts to have an enumerable infinity of symbols). The differences
from our point of view between the single and compound symbols is that
the compound symbols, if they are too lengthy, cannot be observed at one
glance. This is in accordance with experience. We cannot tell at a glance
whether 9999999999999999 and 999999999999999 are the same.
The behaviour of the computer at any moment is determined by the symbols
which he is observing. and his “state of mind” at that moment.
We may suppose that there is a bound B to the number of symbols
or squares which the computer can observe at one moment. If he wishes
to observe more, he must use successive observations. We will also suppose
that the number of states of mind which need be taken into account is
finite. The reasons for this are of the same character as those which
restrict the number of symbols. If we admitted an infinity of states of
mind, some of them will be “arbitrarily close” and will be
confused. Again, the restriction is not one which seriously affects computation,
since the use of more complicated states of mind can be avoided by writing
more symbols on the tape.
Let us imagine the operations performed by the computer to be split up
into “simple operations” which are so elementary that it is
not easy to imagine them further divided. Every such operation consists
of some change of the physical system consisting of the computer and his
tape. We know the state of the system if we know the sequence of symbols
on the tape, which of these are observed by the computer (possibly with
a special order), and the state of mind of the computer. We may suppose
that in a simple operation not more than one symbol is altered. Any other
changes can be set up into simple changes of this kind. The situation
in regard to the squares whose symbols may be altered in this way is the
same as in regard to the observed squares. We may, therefore, without
loss of generality, assume that the squares whose symbols are changed
are always “observed” squares.
Besides these changes of symbols, the simple operations must include
changes of distribution of observed squares. The new observed squares
must be immediately recognisable by the computer. I think it is reasonable
to suppose that they can only be squares whose distance from the closest
of the immediately previously observed squares does not exceed a certain
fixed amount. Let us say that each of the new observed squares is within L squares of an immediately previously observed square. In connection
with “immediate recognisability”, it may be thought that there
are other kinds of square which are immediately recognisable. In particular,
squares marked by special symbols might be taken as imme- {251}diately
recognisable. Now if these squares are marked only by single symbols there
can be only a finite number of them, and we should not upset our theory
by adjoining these marked squares to the observed squares. If, on the
other hand, they are marked by a sequence of symbols, we cannot regard
the process of recognition as a simple process. This is a fundamental
point and should be illustrated. In most mathematical papers the equations
and theorems are numbered. Normally the numbers do not go beyond (say)
1000. It is, therefore, possible to recognise a theorem at a glance by
its number. But if the paper was very long, we might reach Theorem 157767733443477;
then, farther on in the paper, we might find “... hence (applying
Theorem 157767733443477) we have...”. In order to make sure which
was the relevant theorem we should have to compare the two numbers figure
by figure, possibly ticking the figures off in pencil to make sure of
their not being counted twice. If in spite of this it is still thought
that there are other “immediately recognisable” squares, it
does not upset my contention so long as these squares can be found by
some process of which my type of machine is capable. This idea is developed
in III below.
The simple operations must therefore include:
(a) Changes of the symbol on one of the observed squares.
(b) Changes of one of the squares observed to another square
within L squares of one of the previously observed squares.
It may be that some of these changes necessarily involve a change of
state of mind. The most general single operation must therefore be taken
to be one of the following:
A. A possible change (a) of symbol together with a possible
change of state of mind.
B. A possible change (b) of observed squares, together with
a possible change of state of mind.
The operation actually performed is determined, as has been suggested
on p.250, by the state of mind of the computer and
the observed symbols. In particular, they determine the state of mind
of the computer after the operation is carried out.
We may now construct a machine to do the work of this computer. To each
state of mind of the computer corresponds an “m-configuration”
of the machine. The machine scans B squares corresponding to
the B squares observed by the computer. In any move the machine
can change a symbol on a scanned square or can change anyone of the scanned
squares to another square distant not more than L squares from
one of the other scanned {252} squares. The move which is done, and the succeeding configuration, are
determined by the scanned symbol and the m-configuration. The
machines just described do not differ very essentially from computing
machines as defined in §2, and corresponding
to any machine of this type a computing machine can be constructed to
compute the same sequence, that is to say the sequence computed by the
computer.
II. [Type (b)].
If the notation of the Hilbert functional calculus[7] is
modified so as to be systematic, and so as to involve only a finite number
of symbols, it becomes possible to construct an automatic[8] machine K which will find all the provable formulae of the calculus.[9]
Now let α be a sequence, and let us denote
by Gα(x) the proposition
“The x-th figure of α is 1”,
so that [10] – Gα(x) means “The x-th figure of α is 0”. Suppose further that we can find a set of properties which
define the sequence α and which can be expressed
in terms of Gα(x) and of
the propositional functions N(x) meaning
“x is a non-negative integer” and F(x,y)
meaning “y = x + 1”. When we join all these
formulae together conjunctively we shall have a formula, U say, which defines α. The terms of U must include the necessary parts of the Peano axioms, viz.,
(Ǝu) N (u)& (x)(N(x)→(Ǝy)F(x,y)) & ( F(x,y)→N(y) ),
which we will abbreviate to P.
When we say “U defines α”,
we mean that –U is not a provable
formula, and also that, for each n, one of the following formulae
(An) or (Bn)
is provable.
U & F(n) →Gα(u(n)), |
(An)[11] |
U & F(n) → ( –Gα(u(n))), |
(Bn) |
where F(n)] stands for F(u, u') & F(u', u'') & … F(u(n-1), u(n)).
{253} I say that α is
then a computable sequence: a machine Kα to computeα can be obtained by a fairly
simple modification of K.
We divide the motion of α into sections. The n-th section is devoted to finding the n-th
figure of α. After the (n –
l)-th section is finished a double colon : : is printed
after all the symbols, and the succeeding work is done wholly on the squares
to the right of this double colon. The first step is to write the letter
“A” followed by the formula (An)
and then “B” followed by (Bn).
The machine Kα then starts to do the work of K, but whenever
a provable formula is found, this formula is compared with (An)
and with (Bn). If it is the same formula
as (An), then the figure “1”
is printed, and the n-th section is finished. If it is (Bn),
then “0” is printed and the section is finished. If it is
different from both, then the work of K is continued from the point at which it had been abandoned. Sooner or
later one of the formulae (An) or (Bn)
is reached; this follows from our hypotheses about α and U, and the known nature of K.
Hence the n-th section will eventually be finished; Kα is circle-free; α is computable.
It can also be shown that the numbers α definable in this way by the use of axioms include all the computable
numbers. This is done by describing computing machines in terms of the
function calculus.
It must be remembered that we have attached rather a special meaning
to the phrase “U defines α ”.
The computable numbers do not include all (in the ordinary sense) definable
numbers. Let δ be a sequence whose n-th
figure is 1 or 0 according as n is or is not satisfactory. It
is an immediate consequence of the theorem of §8 that δ is not computable. It is (so far as
we know at present) possible that any assigned number of figures of δ
can be calculated, but not by a uniform process. When sufficiently many
figures of δ have been calculated, an essentially
new method is necessary in order to obtain more figures.
III. This may be regarded as a modification
of I or as a corollary of II.
We suppose, as in I, that the computation
is carried out on a tape; but we avoid introducing the “state of
mind” by considering a more physical and definite counterpart of
it. It is always possible for the computer to break off from his work,
to go away and forget all about it, and later to come back and go on with
it. If he does this he must leave a note of instructions (written in some
standard form) explaining how the work is to be continued. This note is
the counterpart of the “state of mind”. We will suppose that
the computer works by such a desultory manner that he never does more
than one step at a sitting. The note of instructions must enable him to
carry out one step and write the next note. Thus the state of progress
of the computation at any stage is completely determined by the note of {254} instructions and the symbols
on the tape. That is, the state of the system may be described by a single
expression (sequence of symbols), consisting of the symbols on the tape
followed by Δ (which we suppose not to appear
elsewhere) and then by the note of instructions. This expression may be
called the “state formula”. We know that the state formula
at any given stage is determined by the state formula before the last
step was made, and we assume that the relation of these two formulae is
expressible in the functional calculus. In other words we assume that
there is an axiom U which expresses the rules
governing the behaviour of the computer, in terms of the relation of the
state formula at any stage to the state formula at the proceeding stage.
If this is so, we
can construct a machine to write down the successive state formulae, and
hence to compute the required number. |
10. Examples of large classes of numbers which are computable.
It will be useful to begin with definitions of a computable function
of an integral variable and of a computable variable, etc. There are many
equivalent ways of defining a computable function of an integral variable.
The simplest is, possibly, as follows. If γ
is a computable sequence in which 0 appears infinitely [12] often, and n is an integer, then let us defines ξ(γ,n)
to be the number of figures 1 between the n-th and the (n+1)-th
figure 0 in γ. Then φ(n)
is computable if , for all n and some γ,φ(n = ξ(γ,n).
An equivalent definition is this. Let H(x,y)
mean φ(x) = y. Then if we can find a contradiction-free axiom Uφ, such that Uφ → P, and if for each integer n there
exists and integer N, such thats
Uφ & F(N) →H(u(n), u(φ(n)))
and such that, if m ≠φ(n), then,
for some N ',
Uφ & F(N ' ) →(– H(u(n), u(m)),
then φ may be said to be a computable function.
We cannot define general computable functions of a real variable, since
there is no general method of describing a real number, but we can define
a computable function of a computable variable. If n is satisfactory,
let γn be the number computed by M (n),
and let
αn = tan (π(γn– ½)),
{255} unless γn = 0 or γn= 1, in either of which cases αn = 0. Then, as n runs through the satisfactory numbers,αn runs through the computable numbers.[13] Now let φ (n)
be a computable function which can be shown to be such that for any satisfactory
argument its value is satisfactory.[14] Then the function f, defined by f(αn) = αφ(n),
is a computable function and all computable functions of a computable
variable are expressible in this form.
Similar definitions may be given of computable functions of several variables,
computable-valued functions of an integral variable, etc.
I shall enunciate a number of theorems about computability, but I shall
prove only (ii) and a theorem similar to (iii).
i ) A computable function of a computable function of an integral or
computable variable is computable.
ii ) Any function of an integral variable defined
recursively in terms of computable functions is computable. I.e. if φ(m, n) is computable, and r is some integer, then η(n)
is computable, where
η(0)
= r,
η(n)
= φ(n, η(n –1)).
iii ) If φ(m, n)
is a computable function of two integral variables, then φ(n, n) is a computable function of n.
iv ) If φ(n)
is a computable function whose value is always 0 or 1, then the sequence
whose n-th figure is φ(n)
is computable. Dedekind’s theorem does not hold in the ordinary
form if we replace “real” throughout by ‘computable’.
But it holds in the following form:
v ) If G(α)
is a propositional function of the computable numbers and
a ) (∃α)(∃β){G(α)
& (– G(β))},
b ) G(α) & (–G(β)) → (α <β),
and there is a general process for determining the truth value of G(α),
then {256} there is a computable
number ξ such that
G(α) → α ⩽ ξ,
–G(α) →α ⩾ ξ.
In other words, the theorem holds for any section of the computables such
that there is a general process for determining to which class a given number
belongs.
Owing to this restriction of Dedekind’s theorem, we cannot say
that a computable bounded increasing sequence of computable numbers has
a computable limit. This may possibly be understood by considering a sequence
such as
–1, -½, –-¼,
–1⁄8, –1⁄16, ½, … .
On the other hand, (v) enables us to prove
vi ) If α and β are computable and α < β and φ(α) < 0 < φ(β),
where φ(α) is a computable increasing continuous
function, then there is a unique computable number γ,
satisfying α < γ < β and φ(γ) = 0.
Computable convergence.
We shall say that a sequence βn of computable
numbers converges computably if there is a computable integral
valued function N(ε)
of the computable variable ε, such that we
can show that, if ε > 0
and n > N (ε)
and m > N (ε) ,
then | βn–βm | < ε.
We can then show that
vii ) A power series whose coefficients form a computable sequence of
computable numbers is computably convergent at all computable points in
the interior of its interval of convergence.
viii ) The limit of a computably convergent sequence
is computable.
And with the obvious definition of “uniformly computably convergent”:
ix ) The limit of a uniformly computably convergent computable sequence
of computable functions is a computable function. Hence
x ) The sum of a power series whose coefficients form a computable sequence
is a computable function in the interior of its interval of convergence.
From (viii) and π =
4(l – 1⁄3+1⁄5 – ...) we deduce that π is computable.
From e = 1 + 1 + ½ ! + 1⁄3! … we deduce thate is computable.
{257} From (vi) we deduce that all real algebraic numbers are computable.
From (vi) and (x) we deduce that the real zeros of the Bessel functions
are computable.
Proof of (ii).
Let H(x, y) mean “η(x) = y”,
and let K(x ,y, z) mean�“φ(x, y) = z”. Uφ is the
axiom for φ(x, y).
We take Uφ to be
Uφ & P & (F(x, y) → G(x, y)) & (G(x, y) & G(x, y) → G(x, y))
& (F(r) → H(u, u(r) )) & (F(v, w) & H(v, x) & K(w, x, z) → H(w, z))
& [H(w, z)& G(z ,t) v G(t, z) → (—H(w, t))].
I shall not give the proof of consistency of Uη.
Such a proof may be constructed by the methods used in Hilbert and Bernays, Grundlagen der Mathematik (Berlin, 1934), p.209 et seq.
The consistency is also clear from the meaning.
Suppose that for some n, N, we have shown
Uη & F(N) → H(u(n-1), u(n(n-1))),
then, for some M,
Uφ& F(M) → K((n), u (η(n-1)), u(η(n)) )
Uη & F(M) →F(u(n-1), u(n) & H(u(n-1), u(η(n-1)))
& K(u(n), u(η(n-1)), u(η(n)))
and
Uη & F(M) → [F(u(n-1), u(n) & H(u(n-1), u(η(n-1)))
& K(u(n), u(η(n-1)), u(η(n))) → H(u(n), u(η(n)))].
Hence Uη &F(M) → H(u(n), u(η(n))).
Also Uη & F(r) → H(u(n), u(η(0))).
Hence for each n some formula of the form
Uη & F(M) → H(u(n), u(η(n)))
is provable. Also, if M ' ⩾ M and M '
⩾ m and m ≠ η(u),
then
Uη & F(M ') → G(u(η(n)), u(m)) v G(u(m), u(η(n)))
{258} and
Uη & F(M ') → [{G(u(η(n)),u(m)) v G(u(m), uu(η(n)) & H(u(n), u(η(n))} → (–H(u(n), u(m)))].
Hence Uη & F(M ') →(–H((u(n), u(m)))
The conditions of our second definition of a computable function are
therefore satisfied. Consequently η is a
computable function.
Proof of a modified form of (iii).
Suppose that we are given a machine N, which,
starting with a tape bearing on it ə ə followed
by a sequence of any number of letters “F” on F-squares
and in the m-configuration b, will compute a sequence γn depending on the number n of letters “F”.
If φn(m) is the m-th figure
of γn, then the sequence β whose n-th figure is φn(n) is computable.
We suppose that the table for N has been
written out in such a way that in each line only one operation appears
in the operations column. We also suppose that Ξ, Θ, 0 and 1 do not occur in the table, and we replace ə throughout by Θ, 0 by 0 and 1 by 1. Further substitutions are then
made. Any line of form
we replace by
and any line of the form
|
U |
α |
P0 |
B |
by |
U |
α |
P0 |
re(B, v, h, k) |
and we add to the table the following lines:
|
u |
n |
pe(u1,0) |
|
|
u1 |
R, Pk, R,
PΘ, R,
PΘ |
u2 |
|
|
u2 |
|
re(u3, u3, k, h) |
|
|
u3 |
|
pe(u2, F) |
|
and similar lines with v for u and 1 for 0 together with the following line
We then have the table for the machine N ' which
computes β. The initial m-confguration
is c, and the initial scanned symbol is the
second ə.
{259}
|
11. Application to the Entscheidungsproblem.
The results of §8 have some important applications.
In particular, they can be used to show that the Hilbert Entscheidungsproblem
can have no solution. For the present I shall confine myself to proving
this particular theorem. For the formulation of this problem I must refer
the reader to Hilbert and Ackermann’s Grundzüge der Theoretischen
Logik (Berlin, 1931), chapter 3.
I propose, therefore, to show that there can be no general process for
determining whether a given formula U of
the functional calculus K is provable, i.e.
that there can be no machine which, supplied with any one U of these formulae, will eventually say whether U is provable.
It should perhaps be remarked what I shall
prove is quite different from the well-known results of Gödel [15].
Gödel has shown that (in the formalism of Principia Mathematica)
there are propositions U such that neither U nor –U is provable. As a consequence
of this, it is shown that no proof of consistency of Principia Mathematica
(or of K) can be given within that formalism.
On the other hand, I shall show that there is no general method which
tells whether a given formula U is provable
in K, or, what comes to the same, whether
the system consisting of K with – U adjoined as an extra axiom is consistent.
If the negation of what Gödel has shown had been proved, i.e. if,
for each U, either U or –U is provable, then we should have
an immediate solution of the Entscheidungsproblem. For we can invent a
machine K which will prove consecutively
all provable formulae. Sooner or later K will reach either U or –U.
If it reaches U, then we know that U is provable. If it reaches –U, then,
since K is consistent (Hilbert and Ackermann,
p.65), we know that U is not provable.
Owing to the absence of integers in K the
proofs appear somewhat lengthy. The underlying ideas are quite straightforward.
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.
The interpretations of the propositional functions involved are as follows:
RSi(x, y)
is to be interpreted as “in the complete configuration x (of�M) the symbol on the square y is S ”.
{260} I(x, y)
is to be interpreted as “in the complete configuration x the square y is scanned”.
Kqm (x)
is to be interpreted as “in the complete configuration x the m-configuration is qm.
F(x, y) is to be interpreted as “y is the immediate successor of x”.
Inst{qi Sj Sk Lql}
is to be an abbreviation for
(x, y, x', y') → (RSj(x, y)
&I(x, y) & Kql(x)
& F(x, x') &F(y', y)
→ (I(x', y')
& RSk(x', y)
& Kqr(x')
& (z[F(y', z)
v (RSj(x', z) →RSk(x', z))])}.
Inst{qi Sj Sk Rql}
and Inst{qi Sj Sk Nql}
are to be abbreviations for other similarly constructed expressions.
Let us put the description of M into the
first standard form of §6. This description consists
of a number of expressions such as “qi, Sj, Sk, Lql” (or with R or N substituted for L). Let us form all the corresponding
expressions such as Inst{qi Sj Sk Lql}and
take their logical sum. This we call Des (M).
The formula Un (M) is to be
(∃u)[N (u)
& (x) (N (x) → (∃x') F (x, x'))
& (y, z) (F (y, z) → N (y) & N (z)) & (y)RSu(u, y)
& I(u, u) & Kqi(u) & Des(M)]
→ (∃s)(∃t)[N(s) & N(t) & RSt(s, t)].
[N(u) & ... Des
(M)] may be abbreviated
to A(M).
When we substitute the meanings suggested on p.259 –
60 we find that Un (M) has the interpretation
“in some complete configuration of M, S1(i.e. 0) appears on the tape”.
Corresponding to this I prove that
a ) If S1 appears on the tape in some complete
configuration of M, then Un (M)
is provable.
b ) If Un (M) is provable, then S1 appears on the tape in some complete configuration of M.
When this has been done, the remainder of the theorem is trivial.
{261} LEMMA1. If S1 appears on the tape in some complete configuration of M , then Un (M) is provable.
We have to show how to prove Un (M). Let
us suppose that in the n-th complete configuration the sequence
of symbols on the tape is Sr(n, 0), Sr(n, 1),
...., Sr(n,n)", followed by nothing but
blanks, and that the scanned symbol is the i(n)-th,
and that the m-configuration is qk(n).
Then we may form the proposition
Rr(n, 0)(u(n), u) & Rr(n, 1)(u(n), u' ) & ... & RSr(m, n)(u(n), u(n))
& I(u(n),u((i(n)))
& Kqk(n)(u(n))
& (y) F ((y, u') v F(u, y)
v F(u', y) v ... v F(u(n-1), y)
v RS0(u(n), y))
which we may abbreviate to CCn.
As before, F(u, u' ) & F(u', u' ' )
& ... & F(u(r-1), u(r))
is abbreviated to F(r).
I shall show that all formulae of the form A(M)
& F(n) → CCn (abbreviated to CFn) are provable.
The meaning of CFn is “The n-th complete configuration of�M is so and so”, where “so and so” stands for the actual n-th complete configuration of M.
That CFn should be provable is therefore
to be expected.
CF0 is certainly provable, for
in the complete configuration the symbols are all blanks, the m-configuration
is q1, and the scanned square is u, i.e. CC0 is
(y) RS0(u, y)
& I(u, u) & Kq1(u).
A(M) → CC0 is then trivial.
We next show that CFn → CFn+1 is provable for each n. There are three cases to consider, according as in the move
from the n-th to the (n + l)-th configuration the machine
moves to left or to right or remains stationary. We suppose that the first
case applies, i.e. the machine moves to the left. A similar argument applies
in the other cases. If r (n,i(n)) = a, r (n+1, i (n+1)) = c, k (i(n)) = b, and k (i(n+1)) = d,
then Des(M) must include Inst{qa Sb Sd Lqc} as one of its terms, i.e.
Des(M) → Inst{qa Sb Sd Lqc}.
Hence A(M)
& F(n+1)→ Inst{qa Sb Sd Lqc} & F(n+1).
But
Inst{qa Sb Sd Lqc} & F(n+1)→ (CCn → CCn+1 )
is provable, and so therefore is
A(M) & F(n+1) → ((CCn → CCn+1 )
{262} and A(M)
&F(n)→ CCn) → (A(M)
& F(n+1)→ CCn+1)
i.e. CFn → CFn+1.
CFn is provable for each n.
Now it is the assumption of this lemma that S1 appears somewhere, in some complete configuration, in the sequence of
symbols printed by M; that is, for some integers N, K, CCN has RS1(u(N), u(k)) as one of its terms, and therefore CCN →RS1(u(N), u(K)) is provable. We have then
CCN →RS1(u(N),
u(K))
and A(M)
& F(N) → CCN
We also have (∃u) A(M)
→ (∃u) (∃u' ) ... (∃u(N ' ))
A(M) & F(N),
where N ' = max (N, K). And so
(∃u) A(M ) → ∃u ) (∃u' ) … (∃u (N ' )) RS1(u(N ), u (K )),
(∃u) A(M ) → (∃u) (∃u(N )) (∃u (K ))
(∃u (N ), u(K )),
(∃u) A(M ) → (∃s) (∃t) RS1(s,t),
i.e. Un(M) is provable.
This completes the proof of Lemma 1.
LEMMA 2. If Un(M) is provable,
then S1 appears on the tape in so-complete
configuration of M.
If we substitute any propositional functions for function variables in
a provable formula, we obtain a true proposition. In particular, if we
substitute the meanings tabulated on pp. 259 – 260 in Un(M), we obtain a true proposition with
the meaning “S1 appears somewhere on the tape in some complete configuration of M”.
We are now in a position to show that the Entseheidungsproblem cannot
be solved. Let us suppose the contrary. Then there is a general (mechanical)
process for determining whether Un(M) is
provable. By Lemmas l and 2, this implies that there is a process for
determining whether M ever prints 0, and
this is impossible, by §8. Hence the Entscheidungsproblem
cannot be solved.
In view of the large number of particular cases of solutions of the Entscheidungsproblem
for formulae with restricted systems of quantors, it {263} is interesting to express Un(M) in a form
in which all quantors are at the beginning. Un(M)
is, in fact, expressible in the form
*****(u)((∃x) (w) (∃u1)
... (*****∃un) B, |
(I) |
where B contains no quantors, and n = 6. By unimportant modifications we can
obtain a formula, with all essential properties of Un(M),
which is of form (I) with ****n = 5. |
Added 28 August, 1936. |
APPENDIX. |
Computability and effective calculability
The theorem that all effectively calculable (λ-definable)
sequences are computable and its converse are proved below in outline.
It is assumed that the terms “well-formed formula” (W.F.F.)
and “conversion” as used by Church and Kleene are understood.
In the second of these proofs the existence of several formulae is assumed
without proof; these formulae may be constructed straightforwardly with
the help of, e.g., the results of Kleene in “A theory of
positive integers in formal logic”, American Journal of Math.,
57 (1935), 153-173, 219-244.
The W.F.F. representing an integer n will
be denoted by Nn.
We shall say that a sequence γ whose n-th
figure is φγ(n)
is λ-definable or effectively calculable
if 1+φγ(u) is
a λ-definable function of n, i.e. if there is a W.F.F. Mγ such that, for all integers n,
{Mγ} (Nn)
conv Nφγ(n)+1,
i.e. {Mγ} (Nn) is convertible into λxy.x(x(y)) or into λxy.x(y)
according as the n-th figure of λ is 1 or 0.
To show that every λ-definable sequence γ is computable, we have to show how to construct a machine to compute γ.
For use with machines it is convenient to make a trivial modification
in the calculus of conversion. This alteration consists in using x, x', x' ', ... as variables instead of a, b, c, …. We now construct a machine L which, when supplied with the formula Mγ,
writes down the sequence γ. The construction
of L is somewhat similar to that of the
machine K which proves all provable formulae
of the functional calculus. We first construct a choice machine L1which, if supplied with a W.F.F., M say,
and suitably manipulated, obtains any formula into which M is convertible. L1can then be modified so as to yield an automatic machine L2 which obtains successively all the formulae {264} into which M is convertible (cf-
foot-note p.252). The machine L includes L2 as a part. The motion of the machine L when
supplied with the formula Mγ is divided into
sections of which the n-th is devoted to
finding the n-th figure of γ.
The first stage in this γ-th section is the
formation of {Mγ}
(Nn). This formula
is then supplied to the machine L ,
which converts it successively into various other formulae. Each formula
into which it is convertible eventually appears, and each, as it is found,
is compared with
λx[λx' [{x}({x}(x'))]], i.e. N2,
and with λx[λx' [{x}({x}(x' )]],i.e. N1.
If it is identical with the first of these, then the machine prints the
figure 1 and the n-th section is finished. If it is identical with the
second, then 0 is printed and the section is finished. If it is different
from both, then the work of' L2 is resumed. By hypothesis, {Mγ} (Nn) is convertible into one of the formulae N2 or N1; consequently
the n-th section will eventually be finished,
i.e. the n-th figure of γ will eventually be written down.
To prove that every computable sequence γ is λ-definable, we must show how to and a
formulaMγsuch
that, for all integers n,
{Mγ}
(Nn) conv N1+ φ, (N).
Let M be a machine which computes γ and let us take some description of the complete configurations of M****M by means of numbers, e.g. we may take the D.N of the complete configuration
as described in §6. Let ξ(n) be the D.N of the n-th complete configuration of M.
The table for the machine M gives us a relation
between ξ(n + 1) and ξ(n)
of the form
ξ(n+ 1)
= pγ( ξ(n)),
where pγ is a function of very
restricted, although not usually very simple, form: it is determined by
the table for M. pγ is λ-definable (I omit the proof of this),
i.e. there is a W.F.F. Aγ such that, for all integers n,
{Aγ} (Nξ(n))
conv Nξ(n+1).
Let Uγ stand
for
λu[}{u}(Aγ){(Nr)]
where r = ξ(0);
then, for all integers n,
{Uγ} (Nn)
conv Nξ(n).
{265} It may be proved that there
is a formula λ such that
{{V}(Nξ(n+1))} (Nξ(n)) |
} |
conv N1
conv N2
conv N3 |
if, in going from the n-th to the (n+1)-th
complete configuration, the figure 0 is printed.
if the figure 1 is printed.
otherwise. |
Let Wγ stand
for
λu[}{V}(Aγ){{Uγ}(u)))x({Uγ}(u))]
so that, for each integer n,
}{V}(Nξ(n+1)){ (Nξ(n)) conv {Wγ}
(Nn),
and let Q be a formula such that
}{Q}(Wγ){ (Ns)
conv�Nr(z),
where r(s) is the s-th integer q for which (Wγ)
(Nn) is convertible
into either N1orN2. Then,
if Mγ stands
for
λw[{Wγ}(}{Q}(Wγ){ (w))]
it will have the required property.[16]
The Graduate College,
Princeton University,
New Jersey,
U.S.A.
|
{544} {Proc. London Math. Soc, Ser. 2, Vol. 43,. No. 2198}
ON COMPUTABLE NUMBERS, WITH AN APPLICATION TO THE ENTSCHEIDUNGSPROBLEM.
A CORRECTION
By A. M. Turing
In a paper entitled On computable numbers, with an application
to the Entseheidungsproblem [17] the author
gave a proof of the insolubility of the Entseheidungsproblem of the “engere
Funktionenkalküls”.[18] This proof contained
some formal errors which will be corrected here: there are also some other
statements in the same paper which should be modified, although they are
not actually false as they stand.
The expression for Inst{qi Sj Sk Lql} on p.260 of the paper quoted should read
(x, y, x', y') →}]RSj(x, y)
& I(x, y) & Kql(x) & F(x, x') & F(y', y)[
→ ]I(x', y')
& RSk(x', y)
& Kqi(x' ) & F(y', z) v []RS0(x,z)[
&](RS1)(x, y)→RS1(x', z)[ & ... & ]RSM(x',z)[][{,
S0, S1,
…, SM being the symbols which�M can print. The
statement on p261, line 33, viz.
“Inst{qa Sb Sd Lqc} & Q & F(n+1) → (CCn→ CCn+1)
is provable” is false (even with the new expression for Inst {qa Sb Sd Lqc}): we are
unable for example to deduce F(n+1) → (–F(u,u' ')) and therefore can never use the term
F (y',z) v []RS0(x, z) →RS0(x', z)[ & … & ]RSM(x,z) → RSM(x',z)[]
{545} in Inst {qa Sb Sd Lqc}. To correct
this we introduce a new functional variable G [G(x, y)
to have the interpretation “x precedes y”.]. Then, if Q is an abbreviation
for
(x)(∃ w)(y, z)}F(x, w) & ]F(x, y) → G(x, y)) & F(x, y) & G(z, y) → G(x, y)[
& [G(z, x) v (G(x, y) & F(y, z)) & F(x, y) v F(z, y)) → (–F(x, z))]}
the corrected formula Un(M) is to be
(∃u) A(M) → (∃s)(∃t) RS1(s, t),
where A(M)
is an abbreviation for
Q & (y) RS0(u, y)
& I(u, u) & Kq1(u)
& Des (M).
The statement on p261 (line 33) must then
read
Inst{qa Sb Sd Lqc}
& Q & F(n+1)→ (CCn→ CCn+1)
and line 29 should read
r(n, i(n)) = b, r(n+1, i(n)) = d, k(n) = a, k(n+1) = c.
For the words “logical sum” on p.
260, line 15, read “conjunction”. With these modifications
the proof is correct. Un (M) may be put in
the form (I) (p.263) with n = 4.
Some difficulty arises from the particular manner in which “computable
number” was defined (p.233). If
the computable numbers are to satisfy intuitive requirements we should
have:
If we can give a rule which associates with each
positive integer n two rationals an, bn satisfying an ⩽ an+1 < bn+1 ⩽ bn, bn –an < 2-5, then there is
a computable number α for which an ⩽ α ⩽ bneach n. |
|
(A) |
A proof of this may be given, valid by ordinary mathematical standards,
but involving an application of the principle of excluded middle. On the
other hand the following is false:
There is a rule whereby, given the rule of formation
of the sequence an, bn in (A) we can obtain a D.N. for a machine to compute α . |
|
(B) |
That (B) is false, at least if we adopt the convention that the decimals
of numbers of the form m/2n shall always terminate with zeros, can be seen in this way. Let N be some machine, and define cn as follows: cn = 4 if N has not printed a figure 0 by
the time the n-th complete configuration is reached cn = 4 – 2–m–3 if 0 had first been printed as the m-th {546} complete configuration (m ⩽ n). Put an = cn –
2–n–2, bn = cn +
2–n–2. Then the inequalities of (A) are satisfied, and the first figure of α is 0 if N ever prints 0 and is 1 otherwise.
If (B) were true we should have a means of finding the first figure of α given the D.N. of N : i.e we should be able to determine whether N ever prints 0, contrary to the results of §8 of the paper quoted. Thus although (A) shows that there must be machines
which compute the Euler constant (for example) we cannot at present describe
any such machine, for we do not yet know whether the Euler constant is
of the form m/2.
This disagreeable situation can be avoided by modifying the manner in
which computable numbers are associated with computable sequences, the
totality of computable numbers being left unaltered. It may be done in
many ways [19] of which this is an example. Suppose
that the first figure of a computable sequence γ is i and that this is followed by 1 repeated n times, then by 0 and finally
by the sequence whose r-th figure is cr;
then the sequence γ is to correspond to the
real number
\[(2 i - 1)n + {\sum_{r =1}^\infty} (2{_c}_r - 1) ( \frac 2 3)^r \]
If the machine which computes γ is regarded
as computing also this real number then (B) holds. The uniqueness of representation
of real numbers by sequences of figures is now lost, but this is of little
theoretical importance, since the D.N.’s are not unique in any case.
The Graduate College,
Princeton, N.J.,
U.S.A. |
Published
on the abelard.org web site by permission of the London Mathematical Society.
Originally published by the London Mathematical
Society in Proceedings of the London Mathematical Society,
Series 2, Vol.42 (1936 - 37) pages 230 to 265,
with corrections from Proceedings of the London Mathematical Society,
Series 2, Vol.43 (1937) pages 544 to 546.
|
Endnotes
- [from p.230] Gödel, “Uber formal unentscheidbare Satze
der Principia Mathernatica und verwant der Systeme, I”, Monatshefte
Math. Phys., 38 (1931). 173-198.
- [from p.231] Alonzo Church. “An unsolvable problem of elementary
number theory”, American J of Math., 58(1936), 345
– 363.
- [from p.231] Alonzo Church. “A note on the Entscheidungsprob1em”, J. of Symbolic logic, 1 (1930), 40 – 41.
- In this reproduction, we at abelard.org are using a redrawn blackletter font in place of the High German blackletter
fonts used in Turing’s paper. The typeface used in the original
paper makes it extremely difficult to systematically and fluently distiguish
between letters, especially capital C, capital E and capital S. English
and German blackletter typefaces have, fundamentally, an extremely similar
character set. No doubt, however, they varied widely in detail between
different printing presses. Our conclusion is that this minor modification
to the original typesetting improves the readability of the paper, and
thus conveys Turing’s intent more effectively, without detracting
from the artistry of his intended layout.
November 2019 : The note above was written in 2001, nigh on a decade before the widespread availability of specialist online fonts,
let alone the standardisation of html entities (all the letters, symbols, marks shown on a web page) or methods of coding mathematics and logic using coding systems like MathJax.
- [from p.246] Cf. Hobson, Theory of functions of a real
variable (2nd ed., 1921), 87, 88.
- [from p.249] If we regard a symbol as literally printed on a
square we may suppose that the square is 0 ⩽ x ⩽ 1, 0 ⩽ y ⩽ 1. The symbol is defined
as a set of points in this square, viz. the set occupied by printer’s
ink. If these sets are restricted to be measurable, we can define the
“distance” between two symbols as the cost of transforming
one symbol into the other if the cost of moving unit area of printer’s
ink unit distance is unity, and there is an infinite supply of ink at x = 2, y =
0. With this topology, the symbols form a conditionally compact space.
- [from p.252] The expression “the functional calculus”
is used throughout to mean the restricted Hilbert functional calculus.
- [from p.252] It is most natural to construct first a choice machine
(§2) to do this. But it then easy to construct
the required automatic machine. We can suppose that the choices are
always choices between two possibilities 0 and 1. Each proof will then
be determined by a sequence of choices i 1, i 2, …, i n (i 1 = 0 or 1, i 2 = 0 or 1, …, i n = 0 or 1),
and hence the number 2n + i 1 2n-1 +i 2 2n-2 +...+ i n,
completely determines the proof. The automatic machine carries out successively
proof 1, proof 2, proof 3, ….
- [from p.252] The author has found a description of such a machine.
- [from p.252] The negation sign is written before an expression
and not over it.
- [from p.252] A sequence of r primes is denoted by (r).
- [from p.254] If M computes γ, then
the problem whether γ prints 0 infinitely
often is of the same character as the problem whether M is circle-free.
- [from p.255] A function αn may
be defined in many other ways so as to run through the computable numbers.
- [from p.255] Although it is not possible to find a general process
for determining whether a given number is satisfactory, it is often
possible to show that certain classes of numbers are satisfactory.
- [from p.259] Loc. cit.
- [from p.265] In a complete proof of the λ-definability
of computable sequences it would be best to modify this method by replacing
the numerical description of the complete configurations by a description
which can be handled more easily with our apparatus. let us choose certain
integers to represent the symbols and the m-configurations of the machine.
Suppose that in a certain complete configuration the numbers representing
the successive symbols on the tape are s1s2... sn, that the m-th symbol is scanned,
and that the m-configuration has the number t; then we may represent
this complete configuration by the formula
[[ N S1,N S2,
…, N Sm-1], [N t, N Sm],
[N Sm+1, …, N Sn]]
where [a, b] stands for λu [ {{u}(a)}(b)],
[a, b, c] stands for λu [{ { {u}(a)}(b)}(c)],
etc.
- [from p.544] Proc. London Math. Soc (2) 42 (1936
– 7), 230 – 265.
- [from p.544] The author is indebted to P. Bernays for pointing
out these errors.
- [from p.546] The use of overlapping intervals for the definition
of real numbers is due originally to Brouwer.
The Turing test and intelligence
abelard gives a detailed logical analysis
of the relationship between intelligence and Turing’s proposed test
of intelligence (as outlined in Computing
machinery and intelligence). |
|