Turing paper

ON COMPUTABLE NUMBERS, WIT H AN APPLICATIO N TO TH E ENTSCHEIDUNGSPROBLE M

[Received 28 May, 1936.—Read 12 November, 1936.]

The "computable " numbers ma y be described briefly as th e real numbers whose expressions as a decimal are calculable by finite means. Although th e subject of this paper is ostensibly th e computable numbers. i t is almost equally easy t o define and investigate computable functions of an integral variable or a real or computable variable, computable predicates, and so forth. The fundamental problems involved are, however, th e same in each case, and I have chosen th e computable numbers for explicit treatmen t as involving th e least cumbrous technique. I hope shortly t o give an account of th e relations of th e computable numbers, functions, and so forth to one another This will include a development of th e theory of functions of a real variable expressed in terms of computabl e numbers. According t o my definition, a number is computable if it s decimal can be writte n down by a machine.

I n §§ 9, 10 I give some arguments with th e intention of showing tha t th e computable numbers include all numbers which could naturall y be regarded as computable. I n particular , I show tha t certain large classes of numbers are computable They include, for instance, th e real part s of all algebraic numbers, th e real part s of th e zeros of th e Bessel functions, th e numbers IT, e, etc . The computable numbers do not , however, include all definable numbers, and an example is given of a definable numbe r which is no t computable.

Although th e class of computable numbers is so great, and in man y Avays similar t o th e class of real numbers, i t is nevertheless enumerable I n § 8 1 examine certain arguments which would seem t o prove th e contrary By th e correct application of one of these arguments, conclusions are reached which are superficially similar t o those of Gbdelf. These results

f Godel, " Uber formal unentscheidbare Satze der Principia Mathematica und ver•vvandter Systeme, I" Monatsheftc Math. Phys., 38 (1931), 173-198

hav e valuable applications. I n particular , i t is shown (§11) tha t th e Hilbertia n Entscheidungsproblem can have no solution.

I n a recent paper Alonzo Church f has introduced an idea of "effective calculability", which is equivalent to my "computability", but is very differently defined. Church also reaches similar conclusions abou t th e EntscheidungsproblemJ The proof of equivalence between "computability " an d "effective calculability " is outlined in an appendix t o th e present paper .

1 Computing machines.

We have said tha t th e computable numbers are those whose decimals are calculable by finite means. This requires rathe r more explicit definition. No real attemp t will be made t o justify th e definitions given unti l we reach § 9 Fo r th e presen t I shall only say tha t th e justification lies in th e fact tha t th e huma n memory is necessarily limited.

We may compare a ma n in th e process of computing a real numbe r t o ;i machine which is only capable of a finite numbe r of conditions q1: q2. ... . qI; which will be called " m-configurations " . The machine is supplied with a "tape " (the analogue of paper) runnin g throug h it , an d divided int o sections (called "squares" ) each capable of bearing a "symbol" . At an y moment ther e is jus t one square , say th e r-th , bearing th e symbol <2>(r) which is "i n th e machine" . We ma y call thi s square th e "scanne d square " The symbol on th e scanned square ma y be called th e " scanned symbol" . The "scanne d symbol " is th e only one of which th e machine is, so t o speak, "directl y aware" . However, by altering it s m-configuratio n th e machine can effectively remember some of th e symbols which i t has "seen " (scanned) previously. The possible behaviour of th e machine a t an y moment is determined by th e ra-configuration qn an d th e scanned symbol <S (r). This pai r qn, © (r) will be called th e ' ' configuration'' : thu s th e configuration determines th e possible behaviour of th e machine I n some of th e configurations in which th e scanned square is blan k (i.e. bears no symbol) th e machine writes down a new symbol on th e scanned square : in other configurations i t erases th e scanned symbol. The machine may also change th e square which is being scanned, bu t only b y shifting i t one place t o righ t or left I n additio n t o an y of these operations th e m-configuration ma y be changed. Some of th e symbols writte n down

f Alonzo Church, " An unsolvable problem, of elementary number theory " , American J. of Math., 58 (1936), 345-363.

X Alonzo Church, " A note on the Entscheidungsproblem", J. of Symbolic Logic, 1 (1936), 40-41

will form th e sequence of figures which is th e decimal of th e real number which is being computed The others are jus t rough notes t o "assis t th e memory " I t will only be these rough notes which will be liable t o erasure

I t is my contention tha t these operations include all those which are used in th e computatio n of a number . The defence of this contention will be easier when th e theor y of th e machines is familiar t o th e reader. I n th e nex t section I therefore proceed with th e development of th e theor y and assume tha t i t is understood wha t is mean t b y "machine" , "tape" , "scanned" , etc .

2 Definitions.

Automatic machines.

I f a t each stage th e motion of a machine (in th e sense of § 1) is completely determined b y th e configuration, we shall call th e machine an "automatic machine " (or a-machine).

.For some purposes we might use machines (choice machines or c-manhines) whose motion is onty partiall y determined by th e configuration (hence th e use of th e word "possible " in §1). When such a machine reaches one of these ambiguous configurations, i t cannot go on unti l some arbitrar y choice has been made by an external operator. This would be th e case if we were using machines t o deal with axiomatic systems I n thi s paper I deal only wit h automati c machines, and will therefore often omit th e prefix a-.

Computing machines.

If an a-machine prints two kinds of symbols, of which th e first kind (called figures) consists entirely of 0 and 1 (the others being called symbols of th e second kind), the n th e machine will be called a computing machine. I f th e machine is supplied with a blank tap e and set in motion, startin g from th e correct initia l ra-configuration, th e subsequence of th e sjinbol s printe d by i t which are of th e first kind will be called th e sequence computed by the machine. The real numbe r whose expression as a binar y decimal is obtained b y prefacing thi s sequence b y a decimal point is called th e number computed by the machine.

A t an y stage of th e motion of th e machine, th e number of th e scanned square , th e complete sequence of all symbols on th e tape , an d th e ra-configuration will be said t o describe th e complete configuration a t tha t stage . The changes of th e machine and tap e between successive complete configurations will be called th e moves of th e machine

Circular and circle-free machines.

I f a computing machine never writes down more tha n a finite numbe r of symbols of th e first kind, i t will be called circular. Otherwise i t is said t o b e circle-free.

A machine will be circular if i t reaches a configuration from which ther e is no possible move, or if i t goes on moving, and possibly printin g symbols of th e second kind, bu t canno t prin t an y more symbols of th e first kind Th e significance of th e ter m "circular " will be explained in §8 .

Computable sequences and numbers.

A sequence is said t o be computable if i t can be computed by a circle-free machine A numbe r is computable if i t differs b y a n integer from th e numbe r computed b y a circle-free machine.

We shall avoid confusion b y speaking more often of computabl e sequences tha n of computable numbers .

3. Examples of computing machines.

I . A machine can be constructe d t o compute th e sequence 010101... . The machine is t o hav e th e four m-configurations "b" , "c" , "£" , "c : > an d is capable of printin g " 0 " and " 1 " . The behaviour of th e machine is described in th e following tabl e in which " R " means "th e machine moves so tha t i t scans th e square immediatel y on th e righ t of th e one i t was scanning previously" . Similarly for "L". "E" means "th e scanned symbol is erased " an d "P " stand s for "prints" . This tabl e (and all succeeding table s of th e same kind) is t o be understood t o mean tha t for a configuration described in th e first two columns th e operations in th e thir d column are carried ou t successively, an d th e machine the n goes over int o th e m-configuration described in th e las t column When th e second column is left blank, i t is understood tha t th e behaviour of th e thir d and fourth columns applies for an y symbol an d for no symbol. Th e machine start s in th e m-configuration b with a blan k tape .

Behaviour operations final

I f (contrary t o th e description in § 1) we allow th e letter s L, R t o appea r more tha n once in th e operations column we can simplify th e tabl e considerably.

m-config. symbol None 0 1 operations

R, R, P I R, R, PO final m-config. 6 b b

II As a slightly more difficult example we can construct a machine t o compute th e sequence 001011011101111011111 The machine is t o be capable of five ra-configurations, viz. " o " , " q " , " p " , " f " , " b " and of printin g "o" , "x", "0" , "1" . The first thre e symbols on th e tap e will be " aoO " ; th e other figures follow on alternat e squares On th e intermediat e squares we never prin t anythin g bu t "x". These letter s serve t o " keep th e place " for us and are erased when we have finished with them . We also arrange tha t in th e sequence of figures on alternat e squares ther e shall be no blanks.

Configuration m-config. symbol b Pa , • { ; fAn y (0 or 1) rt J q i [ None 1 g ^ 1 I None fAn y None

Behaviour

operations

R, Po, R, PO. R, R, PO, L, L i?, Px, L, L, L R, R PI , L E, R R L, L R,R PO, L, L

To illustrat e th e working of thi s machine a table is given below of th e first few complete configurations. These complete configurations are described b y writing down th e sequence of symbols which are on th e tape ,

wit h th e m-configuration writte n below th e scanned symbol The successive complete configurations are separate d by colons : 99 0 Oroo O 0:99 0 0:99 0 0 :99 0 0 1 :

b o q q q p

99 0 0 1:99 0 0 1:99 0 0 1:99 0 0 1 :

990 0 1:99 0 0 1 :oa 0 0 1 0:

This tabl e could also be writte n in th e form b :9 9 o 0 0 : 9 9 q 0 0 : ... , (C) in which a space has been made on th e left of th e scanned symbol and the* m-configuration writte n in thi s space. This form is less easy t o follow, but we shall make use of i t late r for theoretica l purposes. The convention of writing th e figures only on alternat e squares is ver y useful: I shall always make use of it I shall call th e one sequence of alternat e squares JF'-squares and th e othe r sequence ^/-squares. The symbols oi •. ^-square s will be liable t o erasure . The symbols on F-square s form a continuous sequence. There are no blanks unti l th e end is reached. There is no need t o have more tha n one jE'-square between each pair of .F-squarcs : an apparen t need of more ^/-squares can be satisfied by having a sufficiently rich variet y of symbols capable of being printe d on ^-squares . If a symbol /3 is on a n F-squar e S an d a symbol a is on th e ^-squar e nex t on th e righ t of S, the n S and /3 will be said t o be marked wit h a. The process of printin g thi s a will be called marking jS (or S) with a.

4. Abbreviated tables.

There are certain type s of process used by nearly all machines, and these, in some machines, are used in man y connections. These processes include copying down sequences of symbols, comparing sequences, erasing all symbols of a given form, etc . Where such processes ar e concerned we can abbreviat e th e table s for th e m-configurations considerably by th e use of "skeleto n tables" I n skeleton table s ther e appea r capita l German letter s and small Greek letters . These are of th e natur e of "variable s '". B y replacing each capita l German lette r throughou t b y a n ^^-configuration

A. M. TURIN G [Nov.

12,

an d each small Greek lette r by a symbol, we obtain th e tabl e for an m-configuration.

The skeleton table s are t o be regarded as nothing bu t abbreviations : the y are no t essential. So long as th e reader understand s how to obtai n th e complete tables from th e skeleton tables, ther e is no need t o give any exac t definitions in thi s connection

Le t us consider an example : m-config.

Symbol Behaviour Final m-config.

L f^G , 95, a )

f(e,S5,a)

fi(6,93,a)

L f(<5,S3,a)

f a no t a R R R f 2 (G ,

Non e R

From th e m-configuration

f(@, 93, a) th e machine finds th e symbol of form a which is farthes t t o th e left (the "firs t a" ) and th e ?w-confi,guration the n becomes (L If ther e is no a the n th e m-configuration becomes 93.

I, 93, a ) 93

I f we were t o replace £ throughou t by q (say), 93 by r, and a. by x, we should have a complete tabl e for th e m-configuration f (q, x, x). f is called an "?/i-configuration function " or "m-function" .

The only expressions which are admissible for substitutio n in a n »i-function are th e m-configurations and symbols of th e machine These hav e t o be enumerated more or less explicitly : the y may include expressions such as p(c, x); indeed the y mus t if there are an y m-functions used a t all. If we did no t insist on thi s explicit eaumeration, bu t simply state d tha t th e machine had certain m-configurations (enumerated) and all m-configuration s obtainable by substitutio n of m-configurations in certain m-function.-J, we .should usually get a n infinity of m-configurations; e.g., we might say tha t th e machine was t o have th e m-configuration q and all m-configurations obtainable by substitutin g an m-configuration for £ in p(£) . Then i t would hav e q, p(q), pfp(q)V p(p(p(q))) , .. . asm-configurations.

Our interpretatio n rule the n is this . We are given th e names of th e ^-configurations of th e machine, mostly expressed in term s of m-functions. We are also given skeleton tables . All we wan t is th e complete tabl e for th e m-configurations of th e machine This is obtained by repeated substitutio n in th e skeleton tables

Further examples.

(I n th e explanation s th e symbol "-> " is used t o signify "th e machine goes int o th e ra-configuration. " )

e((5,23,a) f (e^S , S3, a) , S3, a )

Fro m c(S, 23, a) th e first a is „ ^ erased an d -> (L I f ther e is no c^G, S3, a) # G

c(S3, a)

c(c(S3, a) , 23, a )

Fro m c(S3, a) all letter s a ar e erased an d -»53.

The las t example seems somewhat more difficult t o interpre t tha n most . Le t u s suppose tha t in th e list of m-configurations of some machine ther e appear s c('b, x) (=q , saj'). The tabl e is

c(6; a;)

or q

Or, in greate r detail : q

c(q, 6, x)

e(c(b, x). h, x)

c(q, 6, a;).

c(q , 6, x)

f (ci(q , 6, a.1), t), a )

Cj.(q, I), re) £• q.

I n thi s we could replace cJL(q, h, x) b y q' an d the n give th e tabl e for f (with th e righ t substitutions ) an d eventuall y reach a tabl e in which no m-functions appeared .

, j8)

f (pc^G, j8), €,Q )

Fro m pc (g , /3) th e machine

[An y i?3JR pe^S.jS) P rint s ^ ^ ^ ue (<S j8) \ sequence of sj^mbols an d -> C [Non e P/S 6

I(S) ^ 2

Fro m f'((5: 2J, a) i t does th e

r /g x j ^ G same as for f(6 , S3, a) bu t moves t o th e left before^ <3

f(6,»,o )

f"(S,»,o )

c(S,S3,o)

f(t(6),a3,a )

f(t(S),S8,a )

f'(c-i(S), 55, a )

c(<£, S3, a) Th e machine

c (<l) R pe(€ JS) writes a t th e end th e first symbol marke d a an d -> £ .

The las t line stand s for th e totalit y of lines obtainable from i t by replacing fi by an y symbol which ma y occur on th e tap e of th e machine concerned.

cc(£,S3,a)

c(e(G,S3,a),83,a )

ce(23, a) The machine copies down in order a t th e cc(23,a) ce(ce(83,a),23,a) end all symbols marked a and erases th e letter s a ; ->SS.

vc(G,93,a,j8) f(re 1 (g 3 $B 3 a, i 8),^ 5 a )

rc(£, S3, a, 0) . The machine replaces th e first a by re^^a.f l E,Pp <Z (8 and->g ^ 35 if ther e is no a.

re(S, a, P) re («(» , a, j8), 93, a, j8) «<» ' a> # • Th e machin e re " places all letter s a b y ]S; ->S5.

cr(Ci,23;a) c(tt(G,9$,a,a) , S3,a)

Cr(83, a) differs from ce(23, a) 011137" in tha t th e «(«(5S,a),rc(SS,a,a),a ) letter s a are no t erased The m-configuration cv(5S, a) is take n u p when no letter s "a " are on th e tape .

•r (C. 21, e . a. ,5) f (cpi ^ S(, )S), f(3t, g, j8), a )

cp,(C, 2l,i8) 7 f (cp2(e,2T, y), S(, 7 S

cp.,((S 2(, y) [noty SI.

The first symbol marked a and th e first marked ]8 are compared. If ther e is neither a nor ft, —> (I\ If ther e are bot h and th e symbols are alike, -> (5. Otherwise -> 21.

cpc(6, SI, G, a, jS) cp (c (e((5, S, yS), 6, a) , SI, g, a, ^ )

cpe(S, 21, S, a, j8) differs from cp(§, 21, £, a, j8) in tha t in th e case when ther e is similarity th e first a and /? are erased

cpe^ , Q, a, P) cpe (cpe(Sl, Q, a, j8), 21, 6, a, )3).

cpe(2I, S, a, j8). The sequence of symbols marked a is compared with th e sequence marke d /? -> Q if the y are similar Otherwise -> 21 Some of th e symbols a and /? are erased

JAny [None JAny [None R R R not a

ce2(95, a,

ce3(S5,a,

j8,y )

L

f Any R, E, R Non e

3)> a )

ce(ce(255j8), a )

a) . Th e machin e finds th e las t symbo l of form a. -> @.

pc2(S, a, jS). Th e machin e print s a j8 a t th e end .

ce3(S5,a,j8,y). Th e machin e copies down a t th e en d

ce (ce2(S5,0, y), a) £ rs t t h e symbol s marke d a, the n thos e marke d jS, an d finally thos e marke d y ; i t erases th e symbol s a, /?, y

e1((5)

Fro m e(^ ) th e mark s ar e ,^> erase d from all marke d symbols -> @

5 Enumeration of computable sequences.

A computable sequence y is determined by a description of a machine which computes y. 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.

I t will be useful to put these tables into a kind of standard form In the first place let us suppose tha t the table is given in the same form as the first table, for example, I on p . 233. That is to say, tha t the entry in the operations column is always of one of the forms E :E,R:E,L:Pa: Pa , R: Pa, L:R:L: or no entry a t all. The table can always be put into this form by introducing more m-configurations. Now let us give numbers to the w-configurations, calling them qx, ..., qR, as in §1 . The initial m-configuration is always to be called qv We also give numbers to the symbols #]_,....., Sm

and, in particular , blank = 80, 0 = Slt 1 = S2 The hnes of th e tabl e ar e now of form

Final

m-config. Symbol Operations m-config. to to to

Lines such as to are t o be writte n as to an d lines such as ft t o be writte n as to

I n thi s way we reduce each line of th e tabl e t o a line of one of th e forms (Nj, (N2), (i\y

Fro m each line of form (N^ le t us form a n expression q( Sj]Sb L qm; from each line of form (N2) we form an expression qiSjSkRqm; an d from each line of form (N3) we form an expression #,•#, SkNqm.

Le t us write down all expressions so formed from th e tabl e for th e machine an d separat e the m b y semi-colons I n thi s way we obtai n a complete description of th e machine. I n thi s description we shall replace q{ by th e lette r "D" followed b y th e lette r "A" repeate d i times, an d $,- b y "D " followed b y "C" repeate d j times This new description of th e machine ma y be called th e standard description (S.D). I t is made u p entirely from th e letter s "A", " C" , "D", "L", "R", "N", an d from

I f finally we replace "A" b y "1" , "C" b y "2" , "D" b y "3" , " L" b y "4" , "R" b y c '5" , "N" by "6" , an d "*3> b y £< 7 " we sh,all hav e a description of th e machine in th e form of a n arabic numeral . The integer represented b y thi s numera l ma y be called a description number (D.N) of th e machine. The D.N determine th e S.D and th e structur e of th e

O N COMPUTABLE NUMBERS

machine uniquely. The machine whose D.N is n may be described as

To each computable sequence there corresponds a t least one description number, while t o no description number does there correspond more tha n one computable sequence. The computable sequences and numbers are therefore enumerable.

Let us find a description number for th e machine I of § 3. When we rename th e m-configurations its table becomes:

q-L ^ o *b1} K q2

q2 SQ P8O, R q3

q3 So PS2) R # 4 ft SQ PSo>R ft

Othe r table s coul d b e obtaine d b y addin g irrelevan t line s suc h a s qx Sx PSVR q2

Ou r first standar d for m woul d b e

qxOQOJRq%j q%^o^o-"ft» 2*3®o^2-"ft' ft^o^oRQ\J•

Th e standar d descriptio n i s

DADDCRDAA ;DAADDRDAAA; I^^DDCCtfi)^ ^ \DAAAADDRDA;

A description number is

31332531173113353111731113322531111731111335317 and so is 3133253117311335311173111332253111173111133531731323253117

A number which is a description number of a circle-free machine will be called a satisfactory number. I n § 8 i t is shown tha t there can be no general process for determining whether a given number is satisfactory or not .

6. The universal computing machine.

I t is possible t o invent a single machine which can be used t o compute an y computable sequence. If this machine M is supplied with a tap e on th e beginning of which is writte n th e S.D of some computing machine .At, 8KR. 2 . VOL. 42 . NO . 2144 . B

the n 'It will compute th e same sequence as it I n this section I explain in outline th e behaviour of th e machine. The nex t section is devoted t o giving th e complete tabl e for U .

Le t us first suppose tha t we have a machine it ' which will write down on th e .F-squares th e successive complete configurations of it . These might be expressed in th e same form as on p . 235, using th e second description, (C), with all symbols on one line Or, better , we could transform thi s description (as in §5) b y replacing each ra-configuration b y "D " followed by "A" repeate d th e appropriat e number of times, and b y replacing each symbol b y "D " followed b y "C" repeated th e appropriat e number of times. The numbers of letters' ' A " and' ' C " are to agree with th e numbers chosen in §5, so that , in particular , "0 " is replaced by "DC", "1 " b y "DCC", and th e blanks by "D" . These substitution s are t o be made after th e complete configurations have been pu t together, as in (C). Difficulties arise if we do th e substitutio n first. I n each complete configuratio n th e blanks would all have t o be replaced by " D " , so tha t th e complete configuration would no t be expressed as a finite sequence of symbols.

If in th e description of th e machine I I of § 3 we replace " o " by " DA A " , "a " by "DCCC", "q " by "DAAA", the n th e sequence (C) becomes:

DA .DCCCDCCCDAADCDDC.DCCCDCCCDAAADCDDC:... (CJ

(This is th e sequence of symbols on ^-squares. )

I t is no t difficult t o see tha t if i t can be constructed, the n so can it' . The manner of operation of it ' could be made t o depend on having th e rules of operation {i.e., th e S.D) of i l writte n somewhere within itself {i.e. within il/) ; each step could be carried ou t b y referring t o these rules We hav e only t o regard th e rules as being capable of being take n ou t an d exchanged for others and we have something very akin t o th e universal machine.

One thin g is lacking : a t present th e machine it ' print s no figures. We ma y correct thi s b y printin g between each successive pair of complete configurations th e figures which appear in th e new configuration bu t no t in th e old. Then (C^) becomes

DDA:O:O:DCCCDCCCDAADCDDC:DCCC... (C2)

I t is no t altogether obvious tha t th e ^-square s leave enough room for th e necessary "roug h work" , bu t this is, in fact, th e case.

The sequences of letter s between th e colons in expressions such as (Cj) ma y be used as standar d descriptions of th e complete configurations. When th e letter s are replaced by figures, as in § 5, we shall have a numerical

•description of th e complete configuration, which may be called it s descriptio n number .

7. Detailed description of the universal machine.

A tabl e is given below of th e behaviour of thi s universal machine. The •m-configurations of which th e machine is capable are all those occurring in th e first an d las t columns of th e table , togethe r wit h all those which occur when we write ou t th e unabbreviate d tables of those which appea r in th e tabl e in th e form of m-functions. E.g., e(anf) appears in th e tabl e an d is a n wi-fimction It s unabbreviate d tabl e is (see p 239)

e(anf)

e^anf)

R, E, R e^onf) c(anf) ei(anf) anf

Consequently e1(anf) is a n m-configuration of U . When \l is read y t o star t work th e tap e runnin g throug h i t bears on i t th e symbol a on a n .F-square an d again Q on th e nex t i£-square; after this , on .F-squares only, comes th e S.D of th e machine followed b y a double colon ":: " (a single symbol, on a n .F-square). The S.D consists of a numbe r of instructions , separated b y semi-colons. Eac h instructio n consists of five consecutive part s

(i) "D " followed b y a sequence of letter s "A". This describes th e relevan t m-configuration.

(ii) "JD " followed b y a sequence of letter s " C" . This describes th e scanned symbol.

(iii) "D " followed b y anothe r sequence of letter s "C". This describes th e symbol int o which th e scanned symbol is t o be changed

(iv) " L" , "i2" , or "JV" , describing whether th e machine is t o move t o left, right , or no t a t all.

(v) "D " followed b y a sequence of letter s "A". This describes th e final m-configuration.

The machine U is t o be capable of printin g "A", "0" , ct D" , "0" , •"1" , "u", "v", "w", "z" , "y", "z" . The S.D is formed from ";" , •"A", "C", "D" , "L" , ((R"} "N".

Subsidiary skeleton table.

(Not A R, R con(£, a)

[Nov 12, con(@, a)

con^CE, a)

con2(§, a)

con(@. a) . Startin g from a n J^-square, S say, th e se-

A L, Pa, R con^S, a) quenc e Q o f symbol s de scrib -

A R,Pa,R con^a ) ing a configuration closest on th e righ t of S is marked ou t R, Pa, R con2(§, a) with letter s a. ->@.

D

G No t C R.R

R, Pa, R con 2 (£,a )

The table for U

hx R,R,P:,R,R,PD;R,R,PA anf

anf

font no t z nor R, Pz: L L,L L

con(S, ). I n th e final configuration th e machine i s scanning th e squar e which i s four squares t o th e righ t of th e las t squar e of C. C is left unmarked .

6. The machine print s on th e .F-squares after ->anf.

g(anf1} :) anf The machine mark s th e configuration in th e las t COn (font, y) comp i et e configuration wit h y.!om !om

con (limp, x) font. The machine finds th e las t semi-colon no t marked with z. I t mark s thi s semi-colon with z and th e configuration following i t with x.

Hnr,> cpe(c(fom, x, y), iim, x, y) fmp. The machine compares th e sequences marked x and y. I t erases all letter s x and y. -> Sim if the y are alike. Otherwise ->• font.

anf Taking th e long view, th e las t instruction relevan t t o th e las t configuration is found. I t can be recognised afterwards as th e instruction following th e las t semi-colon marked z. -Mim

Sim

m?3

m?4

mh A no t no t A A . A R,Pu, L, L,Py, R, R Py con ,R ,R (stm2, Sim Sim e(mB, Sim ) 3 2 3 A C [Any [ None L, L, L, L , Pa;, j^ , Z', con P: L, L, L ?, R, R, R •R , 2 2 mf2

D R, Px, L, L, L m?3

no t : R, Pv, L, L, L m!3 : mL mf6 inSt, 0, : xnit

S im. 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 mconfiguration with y. The letters z are erased

mi. The last complete configuration is marked out into four sections. The configiiraration is left unmarked. The symbol directly preceding it is marked with x. The remainder of th e 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. -> $f;.

, u) Sf;. The instructions (marked u) are examined. If it is found tha t they involve "Prin t 0 " or "Prin t 1" , then 0 : or 1: is printed at the end.

in«t fl(t(in«1),tt)

«**• Th e nex t complete configuration is writte n down,. a R, E in^t1(a) carrying out th e marked instrucL)

ce5(o»,.t>, y, x, u, w)

tionsTh e letter s u> v> w> x> V ar e erased -^anf i?)

\nitx{N)

ce5(o», v, x, u, y, w)

ec5(ot>, v, x, y, u, w)

co c(anf)

8. Application of the diagonal process.

I t ma y be though t tha t arguments which prove tha t th e real numbers are no t enumerable would also prove tha t th e computable numbers an d sequences cannot be enumerable*. I t might, for instance, be though t tha t th e limit of a sequence of computable numbers mus t be computable This is clearly only tru e if th e sequence of computable numbers is defined b y some rule

Or we might apply th e diagonal process. "I f th e computable sequences are enumerable, let a/( be th e n-th computable sequence, and let </>;l(ra) be th e ?n-th figure in au. Le t /? be th e sequence with \—<j>n(n) as it s n-th. figure. Since /3 is computable, ther e exists a number K such tha t l—cf)ll(n) = <f)K(n) al l n. Puttin g n = K, w e hav e 1 = 2(f>K(K), i.e. 1 is even. This is impossible. The computable sequences are therefore no t enumerable"

The fallacy in thi s argument lies in th e assumption tha t § is computable. I t would be tru e if we could enumerate th e computable sequences by finite means, bu t th e problem of enumerating computable sequences is equivalent t o th e problem of finding out whether a given number is th e D.N of a circle-free machine, and we have no general process for doing this in a finite number of steps. I n fact, by applying th e diagonal process argument correctly, we can show tha t ther e cannot be an y such general process

The simplest and most direct proof of this is by showing that , if thi s general process exists, the n ther e is a machine which computes /? This proof, although perfectly sound, has th e disadvantage tha t i t may leave th e reader with a feeling tha t "ther e mus t be something wrong" . The proof which I shall give has no t thi s disadvantage, and gives a certain insight into th e significance of th e idea "circle-free" . I t depends no t on constructing /3, bu t on constructing fi', whose n-th. figure is <j>n{n).

* Cf. Hobson, Theory of functions of a real variable (2nd ed., 1921), 87, 88

Le t us suppose tha t ther e is such a process ; tha t is t o say, tha t we can inven t a machine <D- which, when supplied wit h th e S.D of an y computing machine i l will tes t thi s S.D and if i l is circular will mar k th e S.D wit h th e symbol "u" and if i t is circle-free will mar k i t wit h " s " . By combining th e machines <& and U we could construct a machine :l I- t o compute th e sequence j8'. The machine <O- ma y require a tape . We ma y suppose tha t i t uses th e jE'-squares beyond all symbols on .F-squares, an d tha t when i t has reached it s verdict all th e rough work done b y l0- is erased

The machine J i has it s motion divided int o sections. I n th e first N— 1 sections, among other things , th e integers 1, 2,... , N— 1 hav e been writte n down and teste d by th e machine <Q>-. A certain number, say R(N— I), of the m have been found t o be th e D.N' s of circle-free machines. I n th e N-th section th e machine (& test s th e numbe r N. If N is satisfactory, i.e., if i t is th e D.N of a circle-free machine, the n R(N) = l-\-R(N—l) and th e first R{N) figures of th e sequence of which a $£N is N are calculated The R(N)-th figure of thi s sequence is writte n down as one of th e figures of th e sequence/3' computed by Ji . If N is no t satisfactory, the n R(N) = R(N— 1) an d th e machine goes on t o th e (iV-(-l)-th section of it s motion.

Fro m th e construction of J I- we can see tha t .11- is circle-free Each section of th e motion of J i comes t o a n end after a finite numbe r of steps . For , b y our assumption abou t Q, th e decision as t o whethe r N is satisfactor}' is reached in a finite numbe r of steps . If N is no t satisfactory, the n th e JV-th section is finished. If N is satisfactory, thi s means tha t th e machine il(JV) whose D.N is N is circle-free, an d therefore it s J?(iV)-th figure can be calculated in a finite numbe r of steps . When thi s figure has been calculated an d writte n down as th e R(N)-th figure of /3', th e iV-th section is finished. Hence il is circle-free.

Now le t K be th e D.N of Ji . Wha t does J i do in th e K-th. section of it s motion 1 I t mus t tes t whethe r K is satisfactory, giving a verdic t " 5 " or "u". Since K is th e D.N of JI- an d since JI is circle-free, th e verdic t canno t be "u". On th e other han d th e verdic t canno t be "s". Fo r if i t were, the n in th e K-th. section of it s motion J I- would be bound t o compute th e first R(K—1) + 1 = R(K) figures of th e sequence computed b y th e machine with K as it s D.N and t o writ e down th e R(K)-th as a figure of th e sequence computed b y ill. The computatio n of th e first R(K) — l figures would be carried ou t all right , bu t th e instruction s for calculating th e R(K)-th. would amoun t t o "calculat e th e first R(K) figures computed by H and write down th e R(K)-th". This R{K)-th figure would never be found. I.e., 'i-l is circular, contrar y bot h t o wha t we hav e found in th e las t paragrap h an d t o th e verdic t "s" Thus bot h verdicts are impossible an d we conclude tha t ther e can be no machine '0-.

We can show further tha t there can be no machine £• which, when supplied iviih the S.D of an arbitrary machine AV, will determine vjhether AV ever prints a given symbol (0 say).

We will first show that , if ther e is a machine £ , the n ther e is a general process for determining whether a given machine U< print s 0 infinitely often. Le t Jl x be a machine which print s th e same sequence as A\, except tha t in th e position where th e first 0 printe d by .11- stands , A\x print s 0. • U2 is to have th e first two s\aribols 0 replaced by 0, and so on. Thus, if • Uwere t o prin t

the n A\± woul d prin t ABA01AAB0010AB... and .112 would print

ABAoiAAB~00l0AB....

Xow let H ; be a machine which, when supplied with th e S.D of .U, will write down successively th e S.D of .11, of .ll l 5 of • U2, .. . (there is such a machine). We combine V' with I' and obtain a new machine, Xj. I n th e motion of (, first > is used to write down th e S.D of -U, and the n t test s it. : o : iy writte n if i t is found tha t • 11 never print s 0 ; the n ^ writes th e S.D of • II2, and this is tested. : 0 : being printe d if and only if • Ux never print s 0) and so on KOAV le t us tes t .<, with ('. If i t is found tha t X] never print s 0, the n H print s 0 infinitely often; if X j print s 0 sometimes, the n .11 does no t prin t 0 infinitely often.

Similarly there is a general process for determining whether • U- print s 1 infinitely often. By a combination of these processes we have a process for determining whether . U print s an infinity offigures,i.e. we have a process for determining whether .11 is circle-free There can therefore be no machine i .

The expression "ther e is a general process for determining... " ha s been used throughou t this section as equivalent t o "ther e is a machine which will determine .. . " . This usage can be justified if and only if we can justify our definition of "computable" . Fo r each of these "genera l process : ' problems can be expressed as a problem concerning a general process for determining Avhether a given integer n has a propert y G(n) [e.g. G{n) might mean "n is satisfactory " or "n is th e Godel representation of a provable formula"] , an d thi s is equivalent t o computing a numbe r whose n-th. figure is 1 if G (n) is tru e and 0 if i t is false

9. The extent of the computable numbers.

No attemp t has ye t been made t o show tha t th e " computabl e " numbers include all numbers which would naturall y be regarded as computable . Al I argument s which can be given are bound t o be, fundamentally, appeals t o intuition , and for thi s reason rathe r unsatisfactory mathematically . The real question a t issue is " Wha t are th e possible processes which can be carried ou t in computing a number? "

The argument s which I shall use are of thre e kinds.

(a) A direct appeal t o intuition

(6) A proof of th e equivalence of two definitions (in case th e new definition has a greate r intuitiv e appeal).

(c) Giving examples of large classes of numbers which are computable

Once i t is grante d tha t computable numbers are all c: computable"". several other propositions of th e same characte r follow. I n particular , i t follows that , if ther e is a general process for determinin g whethe r a formula of th e Hilber t function calculus is provable, the n th e determinatio n can bo carried ou t b y a machine.

I [Type (a)]. This argumen t is only a n elaboration of th e ideas of § 1

Computing is normally done by writing certain symbols on paper . "We may suppose thi s pape r is divided int o squares like a child's arithmeti c book I n elementary arithmeti c th e two-dimensional characte r of th e paper is sometimes used. Bu t such a use is always avoidable, and I thin k tha t i t will be agreed tha t th e two-dimensional characte r of pape r is no essential of computation . I assume the n tha t th e computatio n is carried ou t on one-dimensional paper, i.e. on a tap e divided int o squares I shall also suppose tha t th e numbe r of symbols which ma y be printe d is finite. If we were t o allow an infinity of symbols, the n ther e would be symbols differing t o an arbitraril y small exten t j . The effect of thi s restriction of th e numbe r of symbols is no t very serious. I t is always possible t o use sequences of symbols in th e place of single symbols. Thus a n Arabic numera l such as

f If we regard a symbol as literally printed on a square we may suppose tha t 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 t o be measurable, we can define th e "distance " between two symbols as th e cost of transforming one symbol into the other if th e cost of moving uni t area of printer' s ink uni t distance is unity , and there is an infinite supply of ink a t x = 2 y = 0 Wit h this topology th e symbols form a conditionally compact space

12,

17 or 999999999999999 is normally treate d as a single symbol. Similarly in an y Europea n language words are treate d as single symbols (Chinese, however, attempt s t o hav e a n enumerable infinity of symbols) The differences from our poin t of view between th e single an d compound symbols is tha t th e compound symbols, if the y are too lengthy, cannot be observed a t one glance This is in accordance with experience We canno t tell a t a glance whether 9999999999999999 and 999999999999999 are th e same.

The behaviour of th e computer a t an y moment is determined by th e symbols which he is observing, and his " stat e of mind " a t tha t moment. We ma y suppose tha t ther e is a bound B t o th e numbe r of symbols or squares which th e computer can observe a t one moment. I f he wishes t o observe more, he mus t use successive observations. We will also suppose tha t th e numbe r of state s of mind which need be take n int o account is finite The reasons for thi s are of th e same character as those which restric t th e numbe r of symbols I f we admitte d an infinity of state s of mind, some of the m will be ' ' arbitraril y close " and will be confused. Again, th e restriction is no t one which seriously affects computation, since th e use of more complicate d state s of mind can be avoided by writing more symbols on th e tape .

Le t us imagine th e operations performed by th e computer t o be split u p int o "simpl e operations " which are so elementary tha t i t is no t easy t o imagine the m further divided Ever y such operation consists of some change of th e physical system consisting of th e computer and his tape We know th e stat e of th e system if we know th e sequence of symbols on th e tape , which of these are observed b y th e computer (possibly with a special order), and th e stat e of mind of th e computer. We may suppose tha t in a simple operation no t more tha n one symbol is altered. Any othe r changes can be split u p int o simple changes of this kind. The situation in regard t o th e squares whose symbols may be altered in this way is the same as in regar d t o th e observed squares. We may, therefore, withou t loss of generality, assume tha t th e squares whose symbols are changed are always "observed " squares.

Besides these changes of symbols, th e simple operations mus t include changes of distributio n of observed squares. The new observed squares mus t be immediately recognisable by th e computer. I thin k i t is reasonable to suppose tha t the y can only be squares whose distance from th e closest of th e immediately previously observed squares does no t exceed a certain fixed amount Le t us say tha t each of th e new observed squares is within L squares of an immediately previously observed square.

I n connection with "immediat e recognisability " , i t ma y be though t tha t ther e ar e othe r kinds of square which are immediately recognisable. I n particular , squares marked by special symbols might be take n as imme-

O N COMPUTABLE NUMBERS. 251

diatel y recognisable. Now if these squares ar e marke d only by single symbols ther e can be only a finite numbe r of them , an d we should no t upse t our theor y b y adjoining these marke d squares t o th e observed squares . If. on th e other hand , the y are marke d b y a sequence of symbols, we canno t regard th e process of recognition as a simple process This is a fundamental poin t and should be illustrated I n most mathematica l paper s th e equations and theorems are numbered. Normally th e number s do no t go beyond (say) 1000. I t is, therefore, possible t o recognise a theorem a t a glance b y it s number . Bu t if th e pape r was ver y long, we migh t reach Theorem 157767733443477 ; then , further on in th e paper , we migh t find ".. hence (applying Theorem 157767733443477) we hav e " I n order t o make sure which was th e relevan t theorem we should have t o compare th e two numbers figure by figure, possibly ticking th e figures off in pencil t o make sure of thei r no t being counted twice. If in spite of thi s i t is still though t tha t ther e are other "immediatel y recognisable" squares, i t does no t upse t my contention so long as these squares can be found by some process of which my typ e of machine is capable This idea is developed in II I below

The simple operations mus t therefore include :

(a) Changes of th e symbol on one of th e observed squares

(6) Changes of one of th e squares observed t o anothe r square within L squares of one of th e previously observed squares

I t ma y be tha t some of these changes necessarily involve a change of stat e of mind The most general single operation mus t therefore be take n t o be one of th e following:

(A) A possible change (a) of symbol togethe r with a possible change of stat e of mind.

(B) A possible change (6) of observed squares, togethe r with a possible change of stat e of mind.

The operation actuall y performed is determined, as has been suggested on p . 250, by th e stat e of mind of th e computer an d th e observed symbols. I n particular , the y determine th e stat e of mind of th e computer after th e operation is carried out .

We ma y now construc t a machine t o do th e work of thi s computer To each stat e of mind of th e compute r corresponds a n " m-configuration " of th e machine The machine scans B squares corresponding t o th e B squares observed by th e computer . I n an y move th e machine can change a symbol on a scanned square or can change an y one of th e scanned squares t o anothe r squar e distan t no t more tha n L squares from one of th e othe r scanned

squares The move which is done, and th e succeeding configuration, are determined by th e scanned symbol and th e m-configuration The machines jus t described do no t differ very essentially from computing machines as defined in § 2, and corresponding t o any machine of thi s typ e a computing machine can be constructed t o compute th e same sequence, tha t is t o say th e sequence computed by th e computer.

II . [Type (6)].

I f th e notatio n of th e Hilber t functional calculus f is modified so as t o be systematic , and so as t o involve onty a finite number of symbols3 i t becomes possible t o construct an automati c J machine 3C, which will find all th e provable formulae of th e calculus§.

Now le t a be a sequence, an d let us denote by Ga(x) th e proposition "Th e rc-th figure of a is 1 " , so that 1 ' —Ga(x) means "Th e z-t h figure of a is 0 " Suppose further tha t we can find a set of properties which define th e sequence a and which can be expressed in term s of Ga(x) an d of th e prepositional functions N(x) meaning "x is a non-negative integer " and F(x, y) meaning "y = x-\-l " . When we join all these formulae together conjunctively, we shall have a formula, % say, which defines a. The term s of 21 mus t include th e necessary part s of th e Peano axioms, viz.,

N(x)-»(3y)F(x, y)) &(F(X, which we will abbreviat e t o P

When we say " 2( defines a", we mean tha t —21 is no t a provable formula, and also that , for each n, one of th e following formulae (A,J or (B J is provable.

%&Ftn^Ga(uW), (A B )« T

where F™ stands for F{u, u') & F(u', u") & F^-v, u™).

f The expression "th e functional calculus " is used throughout to mean the restricted Hilbert functional calculus.

+ I t is most natura l to construct first a choice machine (§ 2) to do this Bu t i t is then easy to construct th e required automatic machine We can suppose tha t the choice3 are always choices between two possibilities 0 and 1. Each proof will then be determined by a sequence of choices ilt i2, ..., •?•„ (ix = 0 or 1, u = 0 or 1, ... , in = 0 or 1), and hence th e number 2" + i1 2"~^-\-i22"---\-...-\-in completely determines th e proof The automatic machine carries ou t successively proof 1, proof 2, proof 3,

§ The autho r has found a description of such a machine

II The negation sign is written before an expression and not over it

*\ A sequence of r primes is denoted by '''-1

I say tha t a is the n a computable sequence : a machine 'JCa t o comput e a can be obtained b y a fairly simple modification of JC

We divide th e motion of Ka int o sections The n-th section is devoted t o finding th e n-t h figure of a After th e (n— l)-t h section is finished a doubl e colon : : is printe d after all th e symbols, and th e succeeding work is done wholly on th e squares t o th e righ t of thi s double colon. The first ste p is t o write th e lette r "A " followed by th e formula (An) and the n " B " followed b y (B n ) . The machine Ka the n start s t o do th e work of JC, bu t whenever a provable formula is found, thi s formula is compared wit h (An) and wit h (B n ) If i t is th e same formula as (An), the n th e figure " 1 " is printed , an d th e n-th. section is finished. If i t is (B,J, the n " 0 " is printe d an d th e section is finished. If i t is different from both , the n th e work of K is continued from th e point a t which i t ha d been abandoned. Sooner or late r one of th e formulae (An) or (B?1) is reached ; thi s follows from our hypotheses abou t a and 21, an d th e known natur e of JC Hence th e n-th section will eventually be finished. 3CO is circle-free; a is computable

I t can also be shown tha t th e numbers a definable in thi s way by th e use of axioms include all th e computable numbers . This is done b y describing computing machines in term s of th e function calculus.

I t mus t be remembered tha t we hav e attache d rathe r a special meaning t o th e phrase " 21 defines a " The computable numbers do no t include all (in th e ordinary sense) definable numbers . Le t 8 be a sequence whose n-th figure is 1 or 0 according as n is or is no t satisfactory. I t is an immediat e consequence of th e theorem of § 8 tha t 8 is no t computable . I t is (so far as we know a t present) possible tha t an y assigned numbe r of figures of 8 can be calculated, bu t no t b y a uniform process When sufficiently many figures of 8 have been calculated, an essentially new metho d is necessaiy in order t o obtai n more figures.

III . This may be regarded as a modification of I or as a corollary of II .

We suppose, as in I , tha t th e computatio n is carried ou t on a tape ; bu t we avoid introducing th e "stat e of mind " b y considering a more physical and definite counterpar t of it I t is always possible for th e computer t o break off from his work, t o go away and forget all abou t it , and late r t o come back and go on with it . If he does thi s he mus t leave a not e of instructions (written in some standar d form) explaining how th e work is t o be continued . This not e is th e counterpar t of th e "stat e of mind" . We will suppose tha t th e computer works in such a desultory manner tha t he never does more tha n one step a t a sitting . The not e of instructions mus t enable him to carr y ou t one ste p and write th e nex t note . Thus th e stat e of progress of th e computatio n a t an y stage is completely determined by th e not e of

instruction s and th e symbols on th e tape Tha t is, th e stat e of th e system ma y be described by a single expression (sequence of symbols), consisting of th e symbols on th e tap e followed by A (which we suppose no t t o appea r elsewhere) an d the n b y th e not e of instructions . This expression ma y be called th e "stat e formula" . We know tha t th e stat e formula a t an y given stage is determined by th e stat e formula before th e las t ste p was made, and we assume tha t th e relation of these two formulae is expressible in th e functional calculus. I n othe r words, we assume tha t ther e is an axiom 2( which expresses th e rules governing th e behaviour of th e computer, in term s of th e relation of th e stat e formula a t an y stage t o th e stat e formula a t th e preceding stage . If thi s is so, we can construc t a machine t o write down th e successive stat e formulae, and hence t o compute th e required number

10. Examples of large classes of numbers which are computable.

I t will be useful t o begin wit h definitions of a computable function of a n integral variable an d of a computable variable, etc . There are many equivalent ways of defining a computable function of a n integral variable. The simplest is, possibly, as follows. If y is a computable sequence in which 0 appears infinitely ! often, and n is an integer, the n let us define £(y, n) t o be th e number of figures 1 between th e n-th and th e (?i-\- l)-t h figure 0 in y. Then <f)(n) is computable if, for all n an d some y, .<f>(n) = £(y, n). An equivalent definition is this Le t H(x, y) mean <f)(x) = y. Then, if we can find a contradiction-free axiom 21^, such tha t 2^- * P , and if for each integer n ther e exists an integer N, such tha t

% &

an d such that , if m=£<f>(n), then , for some N',

% &

the n <j> may be said t o be a computable function. We cannot define general computable functions of a real variable, since ther e is no general method of describing a real number, bu t we can define a computable function of a computable variable. If n is satisfactory, le t yn be th e number computed by ./U {n), and le t

| If *Al computes y, the n the problem whether .11 print s 0 infinitely often is of the same character as th e problem whether A\, is circle-free

unless yn = 0 or y n — 1, in either of which cases an = 0 Then, as n run s throug h th e satisfactory numbers, a n run s throug h th e computabl e numbersf Now le t <f)(n) be a computable function which can be shown t o be such tha t for an y satisfactory argumen t it s value is satisfactory %. Then th e function / , defined b y f(an) — a^n), is a computabl e function and all computable functions of a computable variable are expressible in thi s form.

Similar definitions ma y be given of computable functions of several variables, computable-valued functions of a n integra l variable , etc I shall enunciate a numbe r of theorems abou t computability , bu t I shall prove only (ii) an d a theorem similar t o (iii).

(i) A computable function of a computable function of a n integral or computable variable is computable .

(ii) Any function of a n integra l variable defined recursively in term s of computable functions is computable I.e. if 0(ra, n) is computable , and r is some integer, the n rj(n) is computable, where

(iii) If <f> (m, n) is a computable function of two integra l variables, the n <j>{n, n) is a computable function of n.

(iv) If (j>(n) is a computable function whose value is always 0 or 1, the n th e sequence whose fi-th figure is <f>(n) is computable .

Dedekind's theorem does no t hold in th e ordinar y form if we replace *' real' ' throughou t by '' computable'' Bu t i t holds in th e following form :

(v) If G(a) is a propositional function of th e computable numbers and (a) (3a)(3jB){G(a)&(-G(j8))} , (6) Q(a)

an d ther e is a general process for determining th e trut h value of G(a), the n

f A function an may be defined in many other ways so as t o ru n through th e computable numbers

J Although it is not possible t o find a general process for determining whether a given number is satisfactory, it is often possible t o show tha t certain classes of numbers are satisfactory.

ther e is a computable numbe r £ such tha t

I n other words, th e theorem holds for an y section of th e computables such tha t ther e is a general process for determining t o which class a given numbe r belongs.

Owing t o thi s restriction of Dedekind's theorem, we canno t say tha t a computabl e bounded increasing sequence of computable numbers ha s a computabl e limit. This ma y possibly be understood b y considering a sequence such as

On th e other hand , (v) enables us t o prove

(vi) I f a and /? are computable and a < /? and <£(a) < 0 < </>(/?), where (f>(a) is a computable increasing continuous function, the n ther e is a uniqu e computable number y, satisfying a < y < fi and <f>(y) = 0

Computable convergence.

We shall say tha t a sequence fin of computable numbers converges computably if ther e is a computable integral valued function N(e) of th e computable variable e, such tha t we can show that , if e > 0 and n > N(e) and m > N(e), the n \pn j8m| < e

We can the n show tha t

(vii) A power series whose coefficients form a computable sequence of computable numbers is computably convergent a t all computable point s in th e interio r of it s interva l of convergence.

(viii) The limit of a computably convergent sequence is computable

And with th e obvious definition of " uniformly computably convergent" :

(ix) The limit of a uniformly computably convergent computabl e 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 th e interior of it s interva l of convergence

Fro m (viii) and TT— 4(1—i-|--i—...) we deduce tha t TT is computable

Fro m e= l + l+n-j-+»-j+.. we deduce tha t e is computable

Fro m (vi) we deduce tha t all real algebraic numbers are computable .

Fro m (vi) an d (x) we deduce tha t th e real zeros of th e Bessel functions are computable .

Proof of (ii).

Le t H(x, y) mean "r](x) = y", and let K{x, y, z) mean "(f>(x, y) = z". 21^ is th e axiom for <f>(x, y). We tak e 31, t o be

% & P & (F{x, y)-*Q{x, y)) & [G{x, y) & G(y, z)->G(x, z)) & (FW-*H{U, VP>)) & (J(v , w) & #(v , x) & Z(w , x} z)->H(iv, z)) & [£f(w , 2) & ^(2 , <) v (?(<, z )

I shall no t give th e proof of consistency of %n. Such a proof ma y be constructe d b y th e methods used i n Hilber t an d Bernays , Grundlagen der Mathematik (Berlin, 1934), p . 209 et seq. The consistency is also clear from th e meaning.

Suppose that , for some n, N, we have shown % & then , for some M, % & & an d Hence 21, Also ST, &

Hence for each w some formula of th e form is provable. Also, if M'^M and if'^ m an d m^r)(u), the n SI, & FW^G^W), u^) v G(u^m\ 8EB . 2 . VOL. 42 . NO. 2145 .

2( & FW)-^ f {G(u^n^, w(m)) v G(u^m\ &

Henc e 21, & FW"> -> ( -H{u^ n \ u™)).

The conditions of our second definition of a computable function are therefore satisfied. Consequently rj is a computable function.

Proof of a modified form of (iii).

Suppose tha t we are given a machine Tl, which, startin g with a tap e bearing on i t 9 9 followed b y a sequence of an y number of letter s "F" on P-square s and in th e m-configuration b, will compute a sequence yn depending on th e numbe r n of letter s " F " . I f <f>n(m) is th e m-th figure of yv, the n th e sequence /3 whose n-th. figure is <f>n{n) is computable.

We suppose tha t th e tabl e for Tl has been writte n ou t i n such a way tha t in each line only one operation appears in th e operations column. We also suppose tha t S, 0 , 0, and 1 do no t occur in th e table , and we replace 9 throughou t b y 0 , 0 by 0, an d 1 byl . Furthe r substitution s are the n made Any line of form

replace by

an y line of

95

te(23, u, h, k) 93 re(93, t>, h, k)

and we add t o th e tabl e th e following lines : u pe(ul5 0)

Uj R, Pk, R, P0 , R, P 0

u2 re(u 3 , u3, k, h)

u 3 pe(u2, F)

an d simila r line s wit h x> fo r u an d 1 fo r 0 togethe r wit h th e followin g lin e

c R, PE, R, Ph 6

We the n have th e tabl e for th e machine (H/ which computes jS. The initial m-configuration is c, and th e initial scanned symbol is th e second a. w e and by

11. Application to the Entscheidungsproblem.

Th e result s of § 8 hav e some importan t applications. I n particular , the y ca n be used t o show tha t th e Hilber t Entscheidungsproblem can hav e no solution . Fo r th e present I shall confine myself t o proving thi s particula r theorem . Fo r th e formulation of this problem I mus t refer th e reader t o Hilber t and Ackermann's Grundziige der Theoretischen Logik (Berlin, 1931), chapte r 3

I propose, therefore, t o show tha t ther e can be no general process for determinin g whethe r a given formula 2( of th e functional calculus K is provable , i.e. tha t ther e can be no machine which, supplied with an y one 21 of these formulae, will eventuall y say whether 21 is provable.

I t should perhaps be remarked tha t wha t I shall prove is quit e different from th e well-known results of Godelf. G odel has shown tha t (in th e formalism of Principia Mathematica) ther e are propositions 21 such tha t neithe r '21 nor — 21 is provable As a consequence of this , i t is shown tha t no proof •of consistency of Principia Mathematica (or of K) can be given within tha t formalism. On th e other hand , I shall show tha t ther e is no general method which tells whether a given formula % is provable i n K, or, wha t comes t o th e same, whether th e system consisting of K wit h —21 adjoined as a n cextra axiom is consistent.

If th e negation of wha t Godel has shown ha d been proved, i.e if, for each 21, either 21 or — 21 is provable, the n we should have an immediate solution of th e Entscheidungsproblem. Fo r we can inven t a machine JC which will prove consecutively all provable formulae. Sooner or late r JC will reach either 21 or —21. If i t reaches 21, the n we know tha t 2( is provable. If i t reaches — 21, then , since K is consistent (Hilbert and Ackermann, p . 65), we know tha t 21 is no t provable

Owing t o th e absence of integers in K th e proofs appea r somewhat lengthy . The underlying ideas are quit e straightforward.

Corresponding t o each computing machine i t we construc t a formula U n (it ) and we show that , if ther e is a general metho d for determining whether U n (.11) is provable, the n ther e is a general metho d for determining whether i t ever print s 0

The interpretation s of th e propositional functions involved are as follows :

Rst(x> V) i s t o be interprete d as "i n th e complete configuration x (of J/l) th e symbol on th e square y is S".

t Loc. cit.

I(x, y) is t o be interprete d as "i n th e complete configuration x th e square y is scanned" .

KQm(x) is t o be interprete d as "i n th e complete configuration x th e m-configuration is qm

F(x, y) is t o be interprete d as st y is th e immediate successor of x " .

Ins t {qt Sj 8k L 37} is t o be a n abbreviation for

(x, y, x', y') I (BSj(x, y) k I(x, y) k K8i(x) k F(x, x') k F(y', y))

fI{x'iy')kBSk{x',y)kKqi{x')

k (z) \_F{y', z)v(RSj(x, z) + Rak(x', z)

Ins t {q{ 8, Sk R qt} and Ins t {qt 8j Sk N q{]

are t o be abbreviations for other similarly constructed expressions.

Le t us pu t th e description of .11 int o th e first standar d form of § 6. This description consists of a number of expressions such as "q{ 8i Sk Lqt" (or with ROT N substitute d for L). Le t us form all th e corresponding expressions such as Ins t {qt $3- Sk L qt} and tak e thei r logical sum This we call Des(.U).

The formula Un(.U ) is t o be {3u)[N{u) &, (x)(N{x)->{3x')F(x, X'))

&. (y, z)(F(y, z)->N(y) k N(z)) & (y) R>%(% y), & I(u, u) & Kqi{u) & Des(..U)l ->(35) (3 0 [N(s) & N(t) & RSl(s, t)).

[K{u)&... &Des(.U) ] may be abbreviated to A(M). When we substitut e th e meanings suggested on p . 259-60 we find tha t Un(.U ) ha s th e interpretatio n "i n some complete configuration of M, S-^ (i.e. 0) appears on th e tap e " . Corresponding t o this I prove tha t

(a) If Sx appears on th e tap e in some complete configuration of • U, the n Un(U ) is provable.

(b) If Un (• U) is provable, the n 8X appears on th e tap e in some complete configuration of • 11.

When thi s has been done, th e remainder of th e theorem is trivial

LEMMA 1. / / S± appears on the tape in some complete configuration of .At, then Un(.At) is provable.

We hav e t o show how t o prove U n (it) . Le t us suppose tha t in th e n-th complete configuration th e sequence of symbols on th e tap e is &r(n,o)> *^r(n,i)5 •••> $i<n,nh followed b y nothin g bu t blanks, and tha t th e scanned symbol is th e i(n)-th, an d tha t th e m-configuration is q^n). Then we ma y form th e proposition , u) & RSrluJvF>, u') & ... & RSr{H,Mn\ which we ma y abbreviat e t o CCn.

As before, F{u, u') & F{u', u") & .. . & F{u^\ w(r)) is abbreviate d t o F<r).

I shall show tha t all formulae of th e form A{-W) & F™^- CCn (abbreviate d t o CFn) are provable. The meaning of CFn is " The n-th. complete configuration of i t is so an d so " , where "s o and so " stand s for th e actua l n-th. complete configuration of it . Tha t CFn should be provable is therefore t o be expected

CF0 is certainly provable, for in th e complete configuration th e symbols are all blanks, th e m-configuration is qx, an d th e scanned square is u, i.e. CC0 is (y) RSo{u, y) & I(u, u) & KQl(u).

A(o\i)->CC0 is the n trivial .

We nex t show tha t CFn^-CFn+1 is provable for each n. There are thre e cases t o consider, according as in th e move from th e n-th t o th e (n-j-l)-t h configuration th e machine moves t o left or t o righ t or remains stationary . We suppose tha t th e first case applies, i.e. th e machine moves t o th e left A similar argumen t applies in th e othe r cases I f r[n,i(n)}=a, r(n-\-l, i(n-\-l)} = c, k(i(n)j =b, and k(i(n-\-l)) =d, the n Des (it ) mus t include Ins t {qa 8b Sd L q^ as one of it s terms , i.e.

Hence A(.AV) & Fin+n^1nat{qa8b8dLqc} & Bu t Inst {q a Sb 8dLqc} & ^ n+ w ^(CC nis provable, and so therefore is

A (• It) & F(n+»-> (CCn -» C(L . ,

an d (AIM) & F™^CCn) -+ (.4(it ) & F<n+V^CCn+1),

i.e.

CFm-»CF.n+V

CFn is provable for each n. Now i t is th e assumption of thi s lemma tha t 8± appears somewhere, in some complete configuration, in th e sequence of symbols printe d b y M; tha t is, for some integers N, K, CGN ha s RS[(u^N\u^) as one of it s terms , and therefore CCN^RSl{u{N\ u(K)) is provable. We hav e the n

an d

We also hav e

A(.M)&FW->CCN

(3u)A(M)-+(3u)(3uf)... where N' — max (N, K). And so

(3u) A ( U.) -> (3^ 7 ) ) (3uW) RS

(3u)A(M)->(3s)(3t)RSl(s,t),

i.e. Un(-U) is provable

This completes th e proof of Lemma 1

LEMMA 2. / / Un(-U) is provable, then S1 appears on the tape in some complete configuration of M.

If we substitut e an y propositional functions for function variables i n a provable formula, we obtai n a tru e proposition. I n particular , if we substitut e th e meanings tabulate d on pp . 259-260 in Un(^U), we obtai n a tru e proposition with th e meaning " S1 appears somewhere on th e tap e i n some complete configuration of .M".

We are now in a position t o show tha t th e Entscheidungsproblem canno t be solved. Le t us suppose th e contrary . Then ther e is a general (mechanical) process for determining whether Un(.tl ) is provable. B y Lemmas 1 and 2, this implies tha t ther e is a process for determining whether .41 ever print s 0, and this is impossible, by §8. Hence th e Entscheidungsproblem canno t be solved

I n view of th e large number of particula r cases of solutions of th e Entscheidungsproblem for formulae with restricted systems of quantors , i t

1936.]

O N COMPUTABLE NUMBERS. 263

is interestin g t o express Un(ii ) in a form i n which all quantor s are a t th e beginning. Un(At) is, in fact, expressible in th e form {u){3x){w){3u1)...{3un)%, (I) where 95 contains no quantors , an d n = 6. By unimportan t modifications we can obtai n a formula, wit h all essential properties of Un(.it) , which is of form (I) wit h n = 5.

Added 28 August, 1936

APPENDIX .

Computabiliiy and effective calculability

The theorem tha t all effectively calculable (A-definable) sequences are computabl e an d it s converse are proved below in outline I t is assumed, tha t th e term s "well-formed formula " (W.F.F. ) an d "conversio n " as used b y Church an d Kleene are understood . I n th e second of these proofs th e existence of several formulae is assumed withou t proof; these formulae ma y be constructed straightforwardly wit h th e help of, e.g., th e results of Kleene in " A theor y of positive integers in formal logic'", American Journal of Math., 57 (1935), 153-173, 219-244

The W.F.F representing a n integer n will be denoted by Nn We shall sa y tha t a sequence y whose n-th figure is (f>y(n) is A-definable or effectively calculable if l-\-</>y(u) is a A-definable function of n, i.e. if ther e is a W.F.F . My such that , for all integers n,

i.e. {My} (Nn) is convertible int o Xxy.x(x(y)) or int o Xxy.x(y) according as th e n-th figure of A is 1 or 0.

To show tha t every A-definable sequence y is computable, we hav e to show how t o construc t a machine t o compute y. Fo r use wit h machines i t is convenient t o make a trivia l modification in th e calculus of conversion. This alteratio n consists in using x, x', x", as variables instead of a, b, c, ... . We now construc t a machine JL which, when supplied with th e formula My, writes down th e sequence y. The construction of X is somewha t similar t o tha t of th e machine K which proves all provable formulae of th e functional calculus. We first construc t a choice machine £-v which, if supplied with a W.F.F. , M say, an d suitabl y manipulated , obtain s an y formula int o which M is convertible. £± can the n be modified so as t o yield a n automati c machine £-2 which obtain s successively all th e formulae

A M TURIN G [NOV 12,

int o which M is convertible (cf. foot-note p . 252). The machine £> includes ^ 2 a s a P ar ^ . The motion of th e machine X when supplied wit h th e formula My is divided int o sections of which th e n-th. is devoted t o finding th e n-t h figure of y. The first stage in this n-th. section is th e formation of {My} {Nn). This formula is the n supplied t o th e machine £2, which converts i t successively int o various other formulae Eac h formula int o which i t is convertible eventually appears, and each, as i t is found, is compared wit h

an d with Aa:|Aa;'[{a;}(a;')] |, i.e. Nv

I f i t is identical with th e first of these, the n th e machine print s th e figure 1 and th e n-th section is finished. If i t is identical with th e second, the n 0 is printe d and th e section is finished. If i t is different from both , the n th e work of .!!2 is resumed. B y hypothesis, {My}(Nn) is convertible int o one of th e formulae N2 or Nx; consequently th e n-t h section will eventually be finished, i.e. th e n-th. figure of y will eventually be writte n down.

To prove tha t every computable sequence y is A-defUiable, we mus t show how t o find a formula My such that , for all integers n, {My}(Nn)c(mvN1+<j)y{n)

Le t .11 be a machine which computes y and le t us tak e some description of th e complete configurations of -U by means of numbers, e.g. we ma y tak e the D.N of th e complete configuration as described in §6 . Le t £(n) be th e D.N of th e w-th complete configuration of M. The tabl e for th e machine ..U gives us a relation between £(n-\-l) and £(n) of th e form

where py is a function of very restricted, although no t usually very simple, form : i t is determined b y th e tabl e for. U. py is A-defmable (I omit th e proof of this) , i.e. ther e is a W.F.F . Ay such that , for all integers n,

Le t U stan d for Xu[{{u}(Ay))(Nr)], where r=£(0); then , for all integers n, {Uy}(NJ conv N,{n).

Itmaybeprovedthatthereis aformula Vsuchthat

convN1 if,ingoingfromthen-thtothe{n+1)-th

LetWrstandfor completeconfiguration,thefigureOis printed.

conv N2 ifthefigureIisprinted.

convN3 otherwise.

sothat,foreachinteger n, {{V}(Nc<n+1))}(Ntcr,l)conv{Wy}(N,i),

andletQbeaformulasuchthat {{Q}(Wy)}(N8) couvN,{.), wherer(s)isthes-thintegerg_forwhich{Wy}(Nq)isconvertibleintoeither N1orN2•Then,ifM1 standsfor itwillhavetherequiredpropertyt.

TheGraduateCollege, PrincetonUniversity, NewJersey,U.S.A.

t In a complete proof of the 1'.-clefinability of computable sequences it would bo 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 81 82 ... 8,., thatthem-th symbol is scanned, andthat them-configuration has the nwnber t; then we may represent this complete configuration by the formula. [[N,,, N,., ..., N,111_1], [N1, N,,,,], [N,,,.+i• ..., N,,.J],

·where [a, b] stands for >..u [{ {u}(a)J(b)], etc.

[a, b, e] stands for w [ { { {u}(a)}(b)}(e)],

For more information on AI History visit: https://aitoolsexplorer.com/ai-history/