On Computable Numbers, with an Application to the Entscheidungsproblem — TEI-tagged view

Alan M. TuringpersName (1936date). “On Computable Numbers, with an Application to the Entscheidungsproblem.” Proceedings of the London Mathematical Societytitle·j, LondonplaceName.

Object of study — The class of numbersterm·key and functions computableterm·key by a finiteterm·key mechanical procedure.

Research question — What does it mean for a numberterm·key to be computableterm·key, and is every mathematical statement mechanically decidable?

Contribution — Defines the Turing machineterm·dom and the universal machineterm·dom and proves the Entscheidungsproblemterm·dom unsolvable, founding the theory of computation.

Full text — tagged

The reference list is not part of the text we hold for this paper. Our copy was extracted from the publisher's page and the bibliography did not survive that extraction, so the article below ends before its references. Nothing has been removed by us.

230 A. M. TUKING [Nov.

12, ON COMPUTABLE NUMBERSterm·dom, WITH AN APPLICATION TO THE ENTSCHEIDUNGSPROBLEMterm·dom By A. M. TURINGpersName.

[Received 28 May, 1936.—Read 12 November, 1936.] The "computableterm·key" numbersterm·key may be described briefly as the real numbersterm·key whose expressions as a decimalterm·key are calculable by finiteterm·key means. Although the subject of this paper is ostensibly the computable numbersterm·dom. it is almost equally easy to define and investigate computableterm·key functions of an integral variable or a real or computableterm·key variable, computableterm·key predicates, and so forth. The fundamental problems involved are, however, the same in each case, and I have chosen the computable numbersterm·dom for explicit treatment as involving the least cumbrous technique. I hope shortly to give an account of the relations of the computable numbersterm·dom, functions, and so forth to one another. This will include a development of the theory of functions of a real variable expressed in terms of computable numbersterm·dom. According to my definition, a numberterm·key is computableterm·key if its decimalterm·key can be written down by a machineterm·key.

In §§ 9, 10 I give some arguments with the intention of showing that the computable numbersterm·dom include all numbersterm·key which could naturally be regarded as computableterm·key. In particular, I show that certain large classes of numbersterm·key are computableterm·key. They include, for instance, the real parts of all algebraic numbersterm·key, the real parts of the zeros of the Bessel functions, the numbersterm·key IT, e, etc. The computable numbersterm·dom do not, however, include all definable numbersterm·key, and an example is given of a definable numberterm·key which is not computableterm·key.

Although the class of computable numbersterm·dom is so great, and in many Avays similar to the class of real numbersterm·key, it is nevertheless enumerable. In § 81 examine certain arguments which would seem to prove the contrary. By the correct application of one of these arguments, conclusions are reached which are superficially similar to 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.

1936.] ON COMPUTABLE NUMBERSterm·dom.

231 have valuable applications. Hilbertian Entscheidungsproblemterm·dom can have no solution.

In particular, it is shown (§11) that the In a recent paper Alonzo Church f has introduced an idea of "effective calculabilityterm·dom", which is equivalent to my "computabilityterm·dom", but is very differently defined. Church also reaches similar conclusions about the EntscheidungsproblemJ. The proof of equivalence between "computabilityterm·dom" and "effective calculabilityterm·dom" is outlined in an appendix to the present paper.

1. Computing machinesterm·key.

We have said that the computable numbersterm·dom are those whose decimalsterm·key are calculable by finiteterm·key means. This requires rather more explicit definition. No real attempt will be made to justify the definitions given until we reach § 9. For the present I shall only say that the justification lies in the fact that the human memory is necessarily limited.

We may compare a man in the process of computing a real numberterm·key to ;i machineterm·key which is only capable of a finiteterm·key numberterm·key of conditions q1: q2. .... qI; which will be called " m-configurationsterm·def ". The machineterm·key is supplied with a " t a p e" (the analogue of paper) running through it, and divided into sections (called "squares") each capable of bearing a "symbolterm·key". At any moment there is just one square, say the r-th, bearing the symbolterm·key <2>(r) which is "in the machineterm·key". We may call this square the "scanned square ". The symbolterm·key on the scanned square may be called the " scanned symbolterm·key". The "scanned symbolterm·key" is the only one of which the machineterm·key is, so to speak, "directly aware". However, by altering its m-configurationterm·def the machineterm·key can effectively remember some of the symbolsterm·key which it has "seen" (scanned) previously. The possible behaviour of the machineterm·key at any moment is determined by the ra-configuration q n and the scanned symbolterm·key <S (r). This pair qn, © (r) will be called the '' configurationterm·key'': thus the configurationterm·key determines the possible behaviour of the machineterm·key. In some of the configurationsterm·key in which the scanned square is blank (i.e. bears no symbolterm·key) the machineterm·key writes down a new symbolterm·key on the scanned square: in other configurationsterm·key it erases the scanned symbolterm·key. The machineterm·key may also change the square which is being scanned, but only by shifting it one place to right or left. In addition to any of these operations the m-configurationterm·def may be changed. Some of the symbolsterm·key written down f Alonzo Church, " An unsolvable problem, of elementary numberterm·key theory ", American J. of Math., 58 (1936), 345-363.

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

232 A. M. TURINGpersName [Nov. 12, will form the sequence of figures which is the decimalterm·key of the real numberterm·key which is being computed. The others are just rough notes to "assist the It will only be these rough notes which will be liable to erasure. memory ". It is my contention that these operations include all those which are used in the computation of a numberterm·key. The defence of this contention will be easier when the theory of the machinesterm·key is familiar to the reader. In the next section I therefore proceed with the development of the theory and assume that it is understood what is meant by "machineterm·key", "tapeterm·key", "scanned", etc.

Automatic machinesterm·key.

2. Definitions.

If at each stage the motion of a machineterm·key (in the sense of § 1) is completely determined by the configurationterm·key, we shall call the machineterm·key an "automatic machineterm·key" (or a-machine).

.For some purposes we might use machinesterm·key (choice machinesterm·key or c-manhines) whose motion is onty partially determined by the configurationterm·key (hence the use of the word "possible" in §1). When such a machineterm·key reaches one of these ambiguous configurationsterm·key, it cannot go on until some arbitrary choice has been made by an external operator. This would be the case if we were using machinesterm·key to deal with axiomatic systems. In this paper I deal only with automatic machinesterm·key, and will therefore often omit the prefix a-.

Computing machinesterm·key.

If an a-machine prints two kinds of symbolsterm·key, of which the first kind (called figures) consists entirely of 0 and 1 (the others being called symbolsterm·key of the second kind), then the machineterm·key will be called a computing machineterm·key. If the machineterm·key is supplied with a blank tapeterm·key and set in motion, starting from the correct initial ra-configuration, the subsequence of the sjinbols printed by it which are of the first kind will be called the sequence computed by the machineterm·key. The real numberterm·key whose expression as a binary decimalterm·key is obtained by prefacing this sequence by a decimalterm·key point is called the numberterm·key computed by the machineterm·key.

At any stage of the motion of the machineterm·key, the numberterm·key of the scanned square, the complete sequence of all symbolsterm·key on the tapeterm·key, and the ra-configuration will be said to describe the complete configurationterm·key at that stage. The changes of the machineterm·key and tapeterm·key between successive complete configurationsterm·key will be called the moves of the machineterm·key.

1936.] ON COMPUTABLE NUMBERSterm·dom.

233 Circularterm·dom and circle-freeterm·dom machinesterm·key.

If a computing machineterm·key never writes down more than a finiteterm·key numberterm·key of symbolsterm·key of the first kind, it will be called circularterm·dom. Otherwise it is said to be circle-freeterm·dom.

A machineterm·key will be circularterm·dom if it reaches a configurationterm·key from which there is no possible move, or if it goes on moving, and possibly printing symbolsterm·key of the second kind, but cannot print any more symbolsterm·key of the first kind. The significance of the term "circularterm·dom" will be explained in §8.

Computableterm·key sequences and numbersterm·key.

A sequence is said to be computableterm·key if it can be computed by a circle-freeterm·dom machineterm·key. A numberterm·key is computableterm·key if it differs by an integer from the numberterm·key computed by a circle-freeterm·dom machineterm·key.

We shall avoid confusion by speaking more often of computableterm·key sequences than of computable numbersterm·dom.

3. Examples of computing machinesterm·key.

I. A machineterm·key can be constructed to compute the sequence 010101.... The machineterm·key is to have the four m-configurationsterm·def " b ", " c ", " £ ", "c :> and is capable of printing " 0 " and " 1 ". The behaviour of the machineterm·key is described in the following table in which " R " means "the machineterm·key moves so that it scans the square immediately on the right of the one it was scanning previously". Similarly for "L". "E" means "the scanned symbolterm·key is erased" and " P" stands for "prints". This table (and all succeeding tables of the same kind) is to be understood to mean that for a configurationterm·key described in the first two columns the operations in the third column are carried out successively, and the machineterm·key then goes over into the m-configurationterm·def described in the last column. When the second column is left blank, it is understood that the behaviour of the third and fourth columns applies for any symbolterm·key and for no symbolterm·key. The machineterm·key starts in the m-configurationterm·def b with a blank tapeterm·key.

Configurationterm·key Behaviour m-config.

symbolterm·key operations final -config.

None None None None PO, R PI, R 234 A. M. TURINGpersName [NOV. 12, If (contrary to the description in § 1) we allow the letters L, R to appear more than once in the operations column we can simplify the table considerably.

m-config.

symbolterm·key None operations final m-config.

R, R, PI R, R, PO II. As a slightly more difficult example we can construct a machineterm·key to The machineterm·key is to compute the sequence 001011011101111011111 be capable of five ra-configurations, viz. " o ", " q ", "p ", " f ", " b " and of printing " o ", "x", " 0 ", " 1 ". The first three symbolsterm·key on the tapeterm·key will be " aoO " ; the other figures follow on alternate squares. On the intermediate squares we never print anything but "x". These letters serve to " keep the place " for us and are erased when we have finished with them. We also arrange that in the sequence of figures on alternate squares there shall be no blanks.

Configurationterm·key Behaviour m-config.

symbolterm·key operations final m-config.

Pa, R, Po, R, PO. R, R, PO, L, L • { ; rt q fAny (0 or 1) J i [ None 1 g ^ 1I None fAny None i?, Px, L, L, L R, R P I, L E, R L, L R,R PO, L, L q f To illustrate the working of this machineterm·key a table is given below of the first few complete configurationsterm·key. These complete configurationsterm·key are described by writing down the sequence of symbolsterm·key which are on the tapeterm·key, 1936.] ON COMPUTABLE NUMBERSterm·dom.

with the m-configurationterm·def written below the scanned symbolterm·key. successive complete configurationsterm·key are separated by colons.

235 The : 9 90 O r o oO 0 : 9 90 0 : 9 90 : 9 90 0 1: 9 90 0 P 1 : 9 90 0 P 0 1 : 9 90 0 1 9 90 1 : 9 90 0 1 : 9 90 0 1: : o a0 0 1 0: f 9 9 0 0 H - 0: ....

This table could also be written in the form b :9 9 o 0 0 : 9 9 q 0 0 : ..., (C) in which a space has been made on the left of the scanned symbolterm·key and the* m-configurationterm·def written in this space. This form is less easy to follow, but we shall make use of it later for theoretical purposes.

The convention of writing the figures only on alternate squares is very useful: I shall always make use of it. I shall call the one sequence of alternate squares JF'-squares and the other sequence ^/-squares. The symbolsterm·key oi •. ^-squares will be liable to erasure. The symbolsterm·key on F-squares form a continuous sequence. There are no blanks until the end is reached. There is no need to have more than one jE'-square between each pair of .F-squarcs : an apparent need of more ^/-squares can be satisfied by having a sufficiently If a rich variety of symbolsterm·key capable of being printed on ^-squares. symbolterm·key /3 is on an F-square S and a symbolterm·key a is on the ^-square next on the right of S, then S and /3 will be said to be marked with a. The process of printing this a will be called marking jS (or S) with a.

4. Abbreviated tables.

There are certain types of process used by nearly all machinesterm·key, and. these, in some machinesterm·key, are used in many connections. These processes include copying down sequences of symbolsterm·key, comparing sequences, erasing all symbolsterm·key of a given form, etc. Where such processes are concerned we can abbreviate the tables for the m-configurationsterm·def considerably by the use of "skeleton tables". In skeleton tables there appear capital German letters and small Greek letters. These are of the nature of "variables '". By replacing each capital German letter throughout by an ^^-configuration 236 A. M. TURINGpersName [Nov. 12, and each small Greek letter by a symbolterm·key, we obtain the table for an m-configurationterm·def.

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

Symbolterm·key Behaviour Final m-config.

f(e,S5,a) fi(6,93,a) f^G, 95, a) f(<5,S3,a) f2(G, I, 93, a) f a not a None From the m-configurationterm·def f(@, 93, a) the machineterm·key finds the symbolterm·key of form a which is farthest to the left (the "first a") then the ?w-confi,guration and becomes (L If there is no a then the m-configurationterm·def becomes 93.

If we were to replace £ throughout by q (say), 93 by r, and a. by x, we f is called should have a complete table for the m-configurationterm·def f (q, x, x). an "?/i-configuration function" or "m-function".

The only expressions which are admissible for substitution in an »i-function are the m-configurationsterm·def and symbolsterm·key of the machineterm·key. These have to be enumerated more or less explicitly: they may include expressions such as p(c, x); indeed they must if there are any m-functions used at all. If we did not insist on this explicit eaumeration, but simply stated that the machineterm·key had certain m-configurationsterm·def (enumerated) and all m-configurationsterm·def obtainable by substitution of m-configurationsterm·def in certain m-function.-J, we .should usually get an infinity of m-configurationsterm·def; e.g., we might say that the machineterm·key was to have the m-configurationterm·def q and all m-configurationsterm·def obtainable by substituting an m-configurationterm·def for £ in p(£). Then it would have q, p(q), pfp(q)V p(p(p(q))), ... asm-configurations.

Our interpretation rule then is this. We are given the names of the ^-configurations of the machineterm·key, mostly expressed in terms of m-functions. We are also given skeleton tables. All we want is the complete table for the m-configurationsterm·def of the machineterm·key. This is obtained by repeated substitution in the skeleton tables.

1936.] ON COMPUTABLE NUMBERSterm·dom.

237 Further examples.

(In the explanations the symbolterm·key " - >" is used to signify " t he machineterm·key goes into the ra-configuration. . . . ") e((5,23,a) „ c^G, S3, a) # f (e^S, S3, a), S3, a) ^ G From c(S, 23, a) the first a is If there is no erased and -> (L c(S3, a) c(c(S3, a), 23, a) From c(S3, a) all letters a are erased and -»53.

The last example seems somewhat more difficult to interpret than most. Let us suppose that in the list of m-configurationsterm·def of some machineterm·key there appears c('b, x) ( = q, saj'). The table is c(6; a;) Or, in greater detail: e(c(b, x). h, x) c(q, 6, a;).

c(q, 6, x) c(q, 6, x) f (ci(q, 6, a.1), t), a) Cj.(q, I), re) In this we could replace cJL(q, h, 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.

, j8) f (pc^G, j8), € , Q) From pc (g, /3) the machineterm·key [Any i?3JR pe^S.jS) ue (<S j8) \ [None P/S ^ j^ I(S) r/gx f ( 6 , » , o) f " ( S , » , o) 2 G f(t(6),a3,a) f(t(S),S8,a) P r i n ts ^ ^ sequence of sj^mbols and -> C From f'((5: 2J, a) it does the same as for f(6, S3, a) but moves to the left before -^ <3.

c(S,S3,o) c (<l) f'(c-i(S), 55, a) pe(€ JS) c(<£, S3, a). The machineterm·key writes at the end the first symbolterm·key marked a and -> £.

238 A. M. TURINGpersName [NOV. 12, The last line stands for the totality of lines obtainable from it by replacing fi by any symbolterm·key which may occur on the tapeterm·key of the machineterm·key concerned.

cc(£,S3,a) c(e(G,S3,a),83,a) cc(23,a) ce(ce(83,a),23,a) vc(G,93,a,j8) f(re1(g3$B3a,i8),^5a) re^^a.fl E,Pp ce(23, a). The machineterm·key copies down in order at the end all symbolsterm·key marked a and erases the letters a; ->SS.

rc(£, S3, a, 0). The machineterm·key replaces the first a by (8 a n d - > g^ 35 if there is no a.

re(S, a, P) re («(», a, j8), 93, a, j8) «<»' a> #• cr(Ci,23;a) c(tt(G,9$,a,a), S3,a) «(«(5S,a),rc(SS,a,a),a) T he m a c h i ne r e " places all letters a by ]S; ->S5. from Cr(83, a) differs ce(23, a) 011137" in that the letters a are not erased. The m-configurationterm·def cv(5S, a) is taken up when no letters " a" are on the tapeterm·key.

•r (C. 21, e. a. ,5) f ( c p i^ S(, )S), f(3t, g, j8), a) cp,(C, 2l,i8) cp.,((S. 2(, y) [noty f (cp2(e,2T, y), S(, SI.

The first symbolterm·key marked a and the first marked ]8 are compared.

If If there are both and the symbolsterm·key are alike, there is neither a nor ft, —> (I\ -> (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 that in the case when there is similarity the 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 symbolsterm·key marked a is compared with the sequence marked /?. -> Q if they are similar. Otherwise -> 21. Some of the symbolsterm·key a and /? are erased.

1936.] ON COMPUTABLE NUMBERSterm·dom.

239 R R JAny [None JAny [None not a ce2(95, a, ce3(S5,a, j8,y) f Any R, E, R None a). The machineterm·key last symbolterm·key of the finds form a.

-> @.

3)> a ) pc2(S, a, jS). The machineterm·key prints a j8 at the end.

ce(ce(255j8), a) ce3(S5,a,j8,y). The machineterm·key copies down at the end ce (ce2(S5,0, y), a) £ r st the symbolsterm·key marked a, then those marked jS, and finally those marked y; it erases the symbolsterm·key a, /?, y.

e1((5) ,^> From e(^) the marks are erased from all marked symbolsterm·key.

-> @.

5. Enumeration of computableterm·key sequences.

A computableterm·key sequence y is determined by a description of a machineterm·key which computes y. Thus the sequence 001011011101111... is determined by the table on p. 234, and, in fact, any computableterm·key 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:Pa: Pa, R: Pa, L:R:L: or no entry at all. The table can always be put into this form by introducing more m-configurationsterm·def. Now let us give numbersterm·key to the w-configurations, calling them qx, ..., qR, as in §1. The initial m-configurationterm·def is always to be called qv We also give numbersterm·key to the symbolsterm·key #]_,....., Sm 240 A. M. TUBING [Nov. 12, and, in particular, blank = 80, 0 = Slt 1 = S2. The hnes of the table are now of form m-config.

Symbolterm·key Operations Final m-config.

to to Lines such as are to be written as and lines such as to be written as PSk,L PSkiR PSk E, R PS0, R PS,, R In this way we reduce each line of the table to a line of one of the forms (Nj, (N2), (i\y.

From each line of form (N^ from each and from each line of form (N3) we form an expression #,•#, SkNqm.

(N2) we form an expression line of form let us form an expression q( Sj]Sb L qm; qiSjSkRqm; Let us write down all expressions so formed from the table for the In this way we obtain a machineterm·key and separate them by semi-colons. complete description of the machineterm·key. In this description we shall replace q{ by the letter "D" followed by the letter "A" repeated i times, and $,- by repeated j times. This new description of the " D" followed by "C" It is made up machineterm·key may be called the standard description (S.D). 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 c ' 5 ", "N" by " 6 ", and "* 3> by £ <7" we sh,all have a description of the machineterm·key in the form of an arabic numeral. The integer represented by this numeral may be called a description numberterm·key (D.N) of the machineterm·key. The D.N determine the S.D and the structure of the 1936.] ON COMPUTABLE NUMBERSterm·dom.

241 machineterm·key uniquely. The machineterm·key whose D.N is n may be described as To each computableterm·key sequence there corresponds at least one description numberterm·key, while to no description numberterm·key does there correspond more than one computableterm·key sequence. The computableterm·key sequences and numbersterm·key are therefore enumerable.

Let us find a description numberterm·key for the machineterm·key I of § 3. When we rename the m-configurationsterm·def its table becomes: q-L *b 1} K P8O, R PS2) R PSo>R Other tables could be obtained by adding irrelevant lines such as PSVR Our first standard form would be qxOQOJRq%j q%^o^o-"ft» 2*3®o^2-"ft' ft^o^oRQ\J• The standard description is DADDCRDAA ;DAADDRDAAA; I ^ ^ D D C C t f i ) ^^ \DAAAADDRDA; A description numberterm·key is 31332531173113353111731113322531111731111335317 and so is 3133253117311335311173111332253111173111133531731323253117 A numberterm·key which is a description numberterm·key of a circle-freeterm·dom machineterm·key will be In § 8 it is shown that there can be no general called a satisfactory numberterm·key. process for determining whether a given numberterm·key is satisfactory or not.

6. The universal computing machineterm·mth.

It is possible to invent a single machineterm·key which can be used to compute any computableterm·key sequence. If this machineterm·key M is supplied with a tapeterm·key on the beginning of which is written the S.D of some computing machineterm·key .At, 8KR. 2. VOL. 42. NO. 2144.

242 A. M. TURINGpersName [NOV. 12, then 'It will compute the same sequence as i t. In this section I explain in outline the behaviour of the machineterm·key. The next section is devoted to giving the complete table for U.

Let us first suppose that we have a machineterm·key i t' which will write down on the .F-squares the successive complete configurationsterm·key of i t. These might be expressed in the same form as on p. 235, using the second description, (C), with all symbolsterm·key on one line. Or, better, we could transform this description (as in §5) by replacing each ra-configuration by " D" followed by "A" repeated the appropriate numberterm·key of times, and by replacing each symbolterm·key by " D" followed by "C" repeated the appropriate numberterm·key of times. The numbersterm·key of letters'' A " and'' C " are to agree with the numbersterm·key 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 configurationsterm·key have been put together, as in (C). Difficulties arise if we do the substitution first. In each complete configurationterm·key the blanks would all have to be replaced by " D ", so that the complete configurationterm·key would not be expressed as a finiteterm·key sequence of symbolsterm·key.

If in the description of the machineterm·key II of § 3 we replace " o " by " DA A ", " a" by "DCCC", " q" by "DAAA", then the sequence (C) becomes: DA .DCCCDCCCDAADCDDC.DCCCDCCCDAAADCDDC:... (CJ (This is the sequence of symbolsterm·key on ^-squares.) It is not difficult to see that if it can be constructed, then so can i t '. The manner of operation of i t' could be made to depend on having the rules of operation {i.e., the S.D) of il written somewhere within itself {i.e. within i l / ); each step could be carried out by referring to these rules. We have only to regard the rules as being capable of being taken out and exchanged for others and we have something very akin to the universal machineterm·dom.

One thing is lacking : at present the machineterm·key i t' prints no figures. We may correct this by printing between each successive pair of complete configurationsterm·key the figures which appear in the new configurationterm·key but not in the old. Then (C^) becomes DDA:O:O:DCCCDCCCDAADCDDC:DCCC...

(C2) It is not altogether obvious that the ^-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 (Cj) may be used as standard descriptions of the complete configurationsterm·key. When the letters are replaced by figures, as in § 5, we shall have a numerical 1936.] ON COMPUTABLE NUMBERSterm·dom.

243 •description of the complete configurationterm·key, which may be called its description numberterm·key.

7. Detailed description of the universal machineterm·dom.

A table is given below of the behaviour of this universal machineterm·dom. The •m-configurationsterm·def of which the machineterm·key 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 wi-fimction.

Its unabbreviated table is (see p. 239) e(anf) e^anf) not 9 Any None R, E, R e^onf) c(anf) ei(anf) anf Consequently e1(anf) is an m-configurationterm·def of U. When \l is ready to start work the tapeterm·key running through it bears on it the symbolterm·key a on an .F-square and again Q on the next i£-square; after this, on .F-squares only, comes the S.D of the machineterm·key followed by a double colon " : :" (a single symbolterm·key, on an .F-square). The S.D consists of a numberterm·key 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-configurationterm·def.

(ii) "JD" followed by a sequence of letters " C". This describes the scanned symbolterm·key.

(iii) " D" followed by another sequence of letters "C". describes the symbolterm·key into which the scanned symbolterm·key is to be changed.

This (iv) "L ", " i 2 ", or "JV", describing whether the machineterm·key is to move to left, right, or not at all.

(v) " D" followed by a sequence of letters "A".

This describes the final m-configurationterm·def.

The machineterm·key U is to be capable of printing "A", " 0 ", c t D ", " 0 ", • " 1 ", "u", "v", "w", " z ", "y", " z ". The S.D is formed from " ; ", •"A", " D ", " L ", "C", "N".

((R"} 244 A. M. TURINGpersName [Nov. 12, Subsidiary skeleton table.

(Not A R, R con(£, a) L, Pa, R con^S, a) R,Pa,R c o n ^ a) con(@. a). Starting from an J^-square, S say, the seq u e n ce Q of s y m b o ls de scribing a configurationterm·key closest on the right of S is marked out R, Pa, R con2(§, a) with letters a.

->@.

con(@, a) con^CE, a) con2(§, a) R, Pa, R con2(£,a) Not C R.R The table for U.

hx R,R,P:,R,R,PD;R,R,PA anf anf font R, Pz: L con (limp, x) L,L !om !om not z nor Hnr,> cpe(c(fom, x, y), iim, x, y) the machineterm·key con(S, ). In the final configurationterm·key is scanning the square which is four squares to the right of the last square of C. C is left unmarked.

6. The machineterm·key prints on the .F-squares after ->anf.

g(anf1} :) COn (font, y) anf. The machineterm·key marks the configurationterm·key in the last c o m p i e te configurationterm·key with y.

font. The machineterm·key finds semi-colon not the last marked with z. It marks this semi-colon with z and following the configurationterm·key it with x.

fmp. The machineterm·key compares the sequences marked x and y. It erases all letters x and y. -> Sim if they are alike. Otherwise ->• font.

anf. Taking the long view, the last instruction relevant to the last It can be recognised afterwards as the instruction configurationterm·key is found. following the last semi-colon marked z.

-Mim.

ON COMPUTABLE NUMBERSterm·dom.

245 S im. The machineterm·key marks out the instructions. That part of the instructions which refers to operations to be carried out is marked with u, and the final mconfigurationterm·def with y. The letters z are erased.

mi. The last complete configurationterm·key is marked out into four sections. The configiiraration is left unmarked. The symbolterm·key directly preceding it is marked with x. The remainder of the complete configurationterm·key 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 that they involve "Print 0" or "Print 1", then 0: or 1: is printed at the end.

1936.] Sim con (stm2, not A .

R,Pu, R, R not Sim 3 Sim 2 e(mB, L,Py, Sim 3 •mt m?3 m?4 L, L, L, L mf2 , Pa;, j ^, Z', R, Px, L, L, L m?3 not : R, Pv, L, L, L m!3 [Any [ None mf6 con L, L, L ?, R, R, R •R, 22 inSt, 0, : xnit 246 in«t i?) \nitx{N) A. M. T U R I NG [NOV. 12, T he n e xt «**• complete configurationterm·key is written down,. carrying out the marked instruct i o n s - T he l e t t e rs u> v> w> x> V -^anf. are erased.

fl(t(in«1),tt) R, E in^t1(a) ce5(o»,.t>, y, x, u, w) ce5(o», v, x, u, y, w) ec5(ot>, v, x, y, u, w) c(anf) 8. Application of the diagonal process.

It may be thought that arguments which prove that the real numbersterm·key are not enumerable would also prove that the computable numbersterm·dom and It might, for instance, be thought sequences cannot be enumerable*. that the limit of a sequence of computable numbersterm·dom must be computableterm·key. This is clearly only true if the sequence of computable numbersterm·dom is defined by some rule.

Or we might apply the diagonal process. "If the computableterm·key sequences are enumerable, let a/( be the n-th computableterm·key sequence, and let </>;l(ra) be the ?n-th figure in au. Let /? be the sequence with \—<j>n(n) as its n-th. figure. Since /3 is computableterm·key, there exists a numberterm·key K such that l—cf)ll(n) = <f)K(n) all n. Putting n = K, we have 1 = 2(f>K(K), i.e. 1 is even. This is impossible. The computableterm·key sequences are therefore not enumerable".

The fallacy in this argument lies in the assumption that § is computableterm·key. It would be true if we could enumerate the computableterm·key sequences by finiteterm·key means, but the problem of enumerating computableterm·key sequences is equivalent to the problem of finding out whether a given numberterm·key is the D.N of a circle-freeterm·dom machineterm·key, and we have no general process for doing this in a finiteterm·key numberterm·key 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 machineterm·key 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 It depends not on insight into the significance of the idea "circle-freeterm·dom". constructing /3, but 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.

1936.] ON COMPUTABLE NUMBERSterm·dom.

247 Let us suppose that there is such a process; that is to say, that we can invent a machineterm·key <D- which, when supplied with the S.D of any computing machineterm·key il will test this S.D and if il is circularterm·dom will mark the S.D with the symbolterm·key "u" and if it is circle-freeterm·dom will mark it with " s ". By combining the machinesterm·key <& and U we could construct a machineterm·key :l I- to compute the sequence j8'. The machineterm·key <O- may require a tapeterm·key. We may suppose that it uses the jE'-squares beyond all symbolsterm·key on .F-squares, and that when it has reached its verdict all the rough work done by l0- is erased.

The machineterm·key Ji 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 machineterm·key <Q>-. A certain numberterm·key, say R(N— I), of In the N-th them have been found to be the D.N's of circle-freeterm·dom machinesterm·key. section the machineterm·key (& tests the numberterm·key N. If N is satisfactory, i.e., if it is the D.N of a circle-freeterm·dom machineterm·key, then R(N) = l-\-R(N—l) and the first R{N) figures of the sequence of which a $£N is N are calculated. The R(N)-th figure of this sequence is written down as one of the figures of the sequence/3' computed by Ji. If N is not satisfactory, then R(N) = R(N— 1) and the machineterm·key goes on to the (iV-(-l)-th section of its motion.

From the construction of J I- we can see that .11- is circle-freeterm·dom. Each section of the motion of Ji comes to an end after a finiteterm·key numberterm·key of steps. For, by our assumption about Q, the decision as to whether N is satisfactor}' is reached in a finiteterm·key numberterm·key of steps. If N is not satisfactory, then the JV-th section is finished. If N is satisfactory, this means that the machineterm·key il(JV) whose D.N is N is circle-freeterm·dom, and therefore its J?(iV)-th figure can be calculated in a finiteterm·key numberterm·key of steps. When this figure has been calculated and written down as the R(N)-th figure of /3', the iV-th section is finished. Hence il is circle-freeterm·dom.

Now let K be the D.N of Ji. What does Ji do in the K-th. section of its motion 1 It must test whether K is satisfactory, giving a verdict " 5 " Since K is the D.N of JI- and since JI is circle-freeterm·dom, the verdict or "u". 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 J I- would be bound to compute the first R(K—1) + 1 = R(K) figures of the sequence computed by the machineterm·key with K as its D.N and to write down the R(K)-th as a figure of the sequence computed by ill. The computation of the first R(K) — l 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 This R{K)-th figure would never be H and write down the R(K)-th". found. I.e., 'i-l is circularterm·dom, 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 machineterm·key '0-.

248 A. M. TURINGpersName [NOV. 12, We can show further that there can be no machineterm·key £• which, when supplied iviih the S.D of an arbitrary machineterm·key AV, will determine vjhether AV ever prints a given symbolterm·key (0 say).

We will first show that, if there is a machineterm·key £, then there is a general process for determining whether a given machineterm·key . U< prints 0 infinitely often. Let Jl x be a machineterm·key which prints the same sequence as A\, except that in the position where the first 0 printed by .11- stands, A\x prints 0. • U2 is to have the first two s\aribols 0 replaced by 0, and so on. Thus, if • Uwere to print ABAQlAABOQIOAB..., then A\± would print and .112 would print ABA01AAB0010AB...

ABAoiAAB~00l0AB....

Xow let H; be a machineterm·key which, when supplied with the S.D of .U, will write down successively the S.D of .11, of .lll5 of • U2, ... (there is such a machineterm·key). We combine V' with I' and obtain a new machineterm·key, Xj. In the motion of (, first > is used to write down the S.D of -U, and then t tests it.: o: iy written if it is found that • 11 never prints 0; then ^ writes the S.D of • II2, and this is tested.. : 0 : being printed if and only if • Ux never prints 0) and so on. KOAV let us test .<, with ('. If it is found that X] never prints 0, then .H prints 0 infinitely often; if Xj prints 0 sometimes, then .11 does not print 0 infinitely often.

Similarly there is a general process for determining whether • U- prints 1 infinitely often. By a combination of these processes we have a process for determining whether. U prints an infinity of figures, i.e. we have a process for determining whether .11 is circle-freeterm·dom. There can therefore be no machineterm·key i .

The expression "there is a general process for determining..." has been used throughout this section as equivalent to "there is a machineterm·key which will determine ... ". This usage can be justified if and only if we can justify our definition of "computableterm·key". For each of these "general process:' problems can be expressed as a problem concerning a general process for determining Avhether a given integer n has a property G(n) [e.g. G{n) might mean "n is satisfactory" or "n is the Godel representation of a provable formula"], and this is equivalent to computing a numberterm·key whose n-th. figure is 1 if G (n) is true and 0 if it is false.

1936.] Otf COMPUTABLE NUMBERSterm·dom.

249 9. The extent of the computable numbersterm·dom.

No attempt has yet been made to show that the " computableterm·key " numbersterm·key include all numbersterm·key which would naturally be regarded as computableterm·key. Al I 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 numberterm·key?" The arguments which I shall use are of three kinds.

(a) A direct appeal to intuition.

(6) A proof of the equivalence of two definitions (in case the new definition has a greater intuitive appeal).

(c) Giving examples of large classes of numbersterm·key which are computableterm·key. Once it is granted that computable numbersterm·dom are all c: computableterm·key"". 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 bo carried out by a machineterm·key.

I. [Type (a)]. This argument is only an elaboration of the ideas of § 1.

Computing is normally done by writing certain symbolsterm·key 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 I assume then that the computation is carried out on of computation. one-dimensional paper, i.e. on a tapeterm·key divided into squares. I shall also suppose that the numberterm·key of symbolsterm·key which may be printed is finiteterm·key. If we were to allow an infinity of symbolsterm·key, then there would be symbolsterm·key differing to an arbitrarily small extent j. The effect of this restriction of the numberterm·key of symbolsterm·key is not very serious. It is always possible to use sequences of symbolsterm·key in the place of single symbolsterm·key. Thus an Arabic numeral such as f If we regard a symbolterm·key as literally printed on a square we may suppose that the square is 0 < x < 1, 0 < y < 1. The symbolterm·key 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 symbolsterm·key as the cost of transforming one symbolterm·key 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 symbolsterm·key form a conditionally compact space.

250 A. M. TUBING [NOV. 12, 17 or 999999999999999 is normally treated as a single symbolterm·key. Similarly in any European language words are treated as single symbolsterm·key (Chinese, however, attempts to have an enumerable infinity of symbolsterm·key). The differences from our point of view between the single and compound symbolsterm·key is that the compound symbolsterm·key, 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 symbolsterm·key which he is observing, and his " state of mind " at that moment. We may suppose that there is a bound B to the numberterm·key of symbolsterm·key 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 numberterm·key of states of mind which need be taken into account is finiteterm·key. The reasons for this are of the same character as those which restrict the numberterm·key of symbolsterm·key. 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 symbolsterm·key on the tapeterm·key. 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 tapeterm·key. We know the state of the system if we know the sequence of symbolsterm·key on the tapeterm·key, 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 symbolterm·key is altered. Any other changes can be split up into simple changes of this kind. The situation in regard to the squares whose symbolsterm·key 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 symbolsterm·key are changed are always "observed" squares.

Besides these changes of symbolsterm·key, 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 symbolsterm·key might be taken as imme- 1936.] ON COMPUTABLE NUMBERSterm·dom.

251 diately recognisable. Now if these squares are marked only by single symbolsterm·key there can be only a finiteterm·key numberterm·key 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 symbolsterm·key, 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 numbersterm·key It is, therefore, possible to recognise a do not go beyond (say) 1000. theorem at a glance by its numberterm·key. But if the paper was very long, we might reach Theorem 157767733443477 ; then, further 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 numbersterm·key 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 machineterm·key is capable. This idea is developed in III below.

The simple operations must therefore include: (a) Changes of the symbolterm·key on one of the observed squares.

(6) 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 symbolterm·key together with a possible change of state of mind.

(B) A possible change (6) 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 symbolsterm·key. In particular, they determine the state of mind of the computer after the operation is carried out.

We may now construct a machineterm·key to do the work of this computer. To each state of mind of the computer corresponds an " m-configurationterm·def " of the machineterm·key. The machineterm·key scans B squares corresponding to the B squares observed by the computer. In any move the machineterm·key can change a symbolterm·key on a scanned square or can change any one of the scanned squares to another square distant not more than L squares from one of the other scanned 252 A. M. TURINGpersName [NOV. 12.

squares. The move which is done, and the succeeding configurationterm·key, are determined by the scanned symbolterm·key and the m-configurationterm·def. The machinesterm·key just described do not differ very essentially from computing machinesterm·key as defined in § 2, and corresponding to any machineterm·key of this type a computing machineterm·key can be constructed to compute the same sequence, that is to say the sequence computed by the computer.

II. [Type (6)].

If the notation of the Hilbert functional calculus f is modified so as to be systematic, and so as to involve onty a finiteterm·key numberterm·key of symbols3 it becomes possible to construct an automatic J machineterm·key 3C, which will find all the provable formulae of the calculus§.

Now let a be a sequence, and let us denote by G a(x) the proposition "The rc-th figure of a is 1 ", so that1' —Ga(x) means "The z-th figure of a is 0 ". Suppose further that we can find a set of properties which define the sequence a and which can be expressed in terms of Ga(x) and of the 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 terms of 21 must include the necessary parts of the Peano axioms, viz., N(x)-»(3y)F(x, y)) &(F(X, which we will abbreviate to P.

When we say " 2( defines a", we mean that —21 is not a provable formula, and also that, for each n, one of the following formulae (A,J or (BJ is provable.

%&Ftn^Ga(uW), (AB)«T where F™ stands for F{u, u') & F(u', u") & ... F^-v, u™).

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

+ It is most natural to construct first a choice machineterm·key (§ 2) to do this. But it is then easy to construct the required automatic machineterm·key. We can suppose that 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 the numberterm·key 2" + i1 2"~^-\-i22"---\-...-\-in completely determines the proof. The automatic machineterm·key carries out successively proof 1, proof 2, proof 3, .... § The author has found a description of such a machineterm·key. II The negation sign is written before an expression and not over it. *\ A sequence of r primes is denoted by '''-1.

1936.] ON COMPUTABLE NUMBERSterm·dom.

253 I say that a is then a computableterm·key sequence: a machineterm·key 'JCa to compute a can be obtained by a fairly simple modification of JC We divide the motion of Ka into sections. The n-th section is devoted to finding the n-th figure of a. After the (n— l)-th section is finished a double colon :: is printed after all the symbolsterm·key, 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 (A n) and then " B " followed by (Bn). The machineterm·key Ka then starts to do the work of JC, 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 (B,J, 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 (B?1) is reached; this follows from our hypotheses about a and 21, and the known nature of JC. Hence the n-th section will eventually be finished. 3CO is circle-freeterm·dom; a is computableterm·key.

It can also be shown that the numbersterm·key a definable in this way by the use of axioms include all the computable numbersterm·dom. This is done by describing computing machinesterm·key in terms of the function calculus.

It must be remembered that we have attached rather a special meaning to the phrase " 21 defines a ". The computable numbersterm·dom do not include all. (in the ordinary sense) definable numbersterm·key. Let 8 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 8 is not computableterm·key. It is (so far as we know at present) possible that any assigned numberterm·key of figures of 8 can be calculated, but not by a uniform process. When sufficiently many figures of 8 have been calculated, an essentially new method is necessaiy 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 tapeterm·key; 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 If he does this he must leave a note of instructions back and go on with it. (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 in 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 A. M. TURINGpersName [NOV. 12, instructions and the symbolsterm·key on the tapeterm·key. That is, the state of the system may be described by a single expression (sequence of symbolsterm·key), consisting of the symbolsterm·key on the tapeterm·key followed by A (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 other words, we assume that there is an in the functional calculus. axiom 2( which expresses the rules governing the behaviour of the computer, in terms of the relation of the state formula at any stage to the If this is so, we can construct a state formula at the preceding stage. machineterm·key to write down the successive state formulae, and hence to compute the required numberterm·key.

10. Examples of large classes of numbersterm·key which are computableterm·key.

It will be useful to begin with definitions of a computableterm·key function of an integral variable and of a computableterm·key variable, etc. There are many integral equivalent ways of defining a computableterm·key function of an variable. The simplest is, possibly, as follows. If y is a computableterm·key sequence in which 0 appears infinitely! often, and n is an integer, then let us define £(y, n) to be the numberterm·key of figures 1 between the n-th and the (?i-\- l)-th figure 0 in y. Then <f)(n) is computableterm·key if, for all n and some y, .<f>(n) = £(y, n). An equivalent definition is this. Let H(x, y) mean <f)(x) = y. Then, if we can find a contradiction-free axiom 21^, such that 2^-* P, and if for each integer n there exists an integer N, such that and such that, if m=£<f>(n), then, for some N', % & % & then <j> may be said to be a computableterm·key function.

We cannot define general computableterm·key functions of a real variable, since there is no general method of describing a real numberterm·key, but we can define a computableterm·key function of a computableterm·key variable. If n is satisfactory, let yn be the numberterm·key computed by ./U {n), and let | If *Al computes y, then the problem whether .11 prints 0 infinitely often is of the same character as the problem whether A\, is circle-freeterm·dom.

1936.] ON COMPUTABLE NUMBERSterm·dom.

255 unless yn = 0 or yn — 1, in either of which cases an = 0. Then, as n runs through the satisfactory numbersterm·key, a n runs through the computableterm·key numbersf. Now let <f)(n) be a computableterm·key function which can be shown to be such that for any satisfactory argument its value is satisfactory %. Then the function /, defined by f(a n) — a^n), is a computableterm·key function and all computableterm·key functions of a computableterm·key variable are expressible in this form.

Similar definitions may be given of computableterm·key functions of several variables, computable-valued functions of an integral variable, etc.

I shall enunciate a numberterm·key of theorems about computabilityterm·dom, but I shall prove only (ii) and a theorem similar to (iii).

(i) A computableterm·key function of a computableterm·key function of an integral or computableterm·key variable is computableterm·key.

(ii) Any function of an integral variable defined recursively in terms of computableterm·key functions is computableterm·key. I.e. if 0(ra, n) is computableterm·key, and r is some integer, then rj(n) is computableterm·key, where (iii) If <f> (m, n) is a computableterm·key function of two integral variables, then <j>{n, n) is a computableterm·key function of n.

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

Dedekind's theorem does not hold in the ordinary form if we replace *' real'' throughout by '' computableterm·key''. But it holds in the following form : (v) If G(a) is a propositional function of the computable numbersterm·dom and (a) (3a)(3jB){G(a)&(-G(j8))}, (6) Q(a) and there is a general process for determining the truth value of G(a), then f A function an may be defined in many other ways so as to run through the computable numbersterm·dom.

J Although it is not possible to find a general process for determining whether a given numberterm·key is satisfactory, it is often possible to show that certain classes of numbersterm·key are satisfactory.

256 A. M. TURINGpersName [NOV. 12r there is a computable numberterm·dom £ such that In other words, the theorem holds for any section of the computablesterm·key such that there is a general process for determining to which class a given numberterm·key belongs.

Owing to this restriction of Dedekind's theorem, we cannot say that a computableterm·key bounded increasing sequence of computable numbersterm·dom has a computableterm·key limit. This may possibly be understood by considering a sequence such as I 2» On the other hand, (v) enables us to prove I i o j I 8' l J-5 1 5' ± 2' • •• • (vi) If a and /? are computableterm·key and a < /? and <£(a) < 0 < </>(/?), where (f>(a) is a computableterm·key increasing continuous function, then there is a unique computable numberterm·dom y, satisfying a < y < fi and <f>(y) = 0.

Computableterm·key convergence.

We shall say that a sequence fi n of computable numbersterm·dom converges computably if there is a computableterm·key integral valued function N(e) of the computableterm·key variable e, such that we can show that, if e > 0 and n > N(e) and m > N(e), then \pn—j8m| < e. We can then show that (vii) A power series whose coefficients form a computableterm·key sequence of computable numbersterm·dom is computably convergent at all computableterm·key points in the interior of its interval of convergence.

(viii) The limit of a computably convergent sequence is computableterm·key.

And with the obvious definition of " uniformly computably convergent": (ix) The limit of a uniformly computably convergent computableterm·key sequence of computableterm·key functions is a computableterm·key function. Hence (x) The sum of a power series whose coefficients form a computableterm·key sequence is a computableterm·key function in the interior of its interval of convergence.

From (viii) and TT— 4(1—i-|--i—...) we deduce that TT is computableterm·key.

From e =l + l+n-j-+»-j+... we deduce that e is computableterm·key.

1936.] OlST COMPUTABLE NUMBERSterm·dom.

257 From (vi) we deduce that all real algebraic numbersterm·key are computableterm·key. From (vi) and (x) we deduce that the real zeros of the Bessel functions are computableterm·key.

Proof of (ii).

Let H(x, y) mean "r](x) = y", and let K{x, y, z) mean "(f>(x, y) = z".

21^ is the axiom for <f>(x, y). We take 31, to 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 not give the proof of consistency of %n. 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 % & then, for some M, % & 21, ST, & and Hence Also Hence for each w some formula of the form is provable. Also, if M'^M and i f ' ^m and m^r)(u), then SI, & FW^G^W), u^) v G(u^m\ 8EB. 2. VOL. 4 2. NO. 2 1 4 5.

258 and A. M. TURINGpersName [NOV. 12, 2( & FW)-^ f {G(u^n^, w(m)) v G(u^m\ Hence 21, & FW"> -> (- H { u ^ n \ u™)).

The conditions of our second definition of a computableterm·key function are therefore satisfied.

Consequently rj is a computableterm·key function.

Proof of a modified form of (iii).

Suppose that we are given a machineterm·key Tl, which, starting with a tapeterm·key bearing on it 9 9 followed by a sequence of any numberterm·key of letters "F" on P-squares and in the m-configurationterm·def b, will compute a sequence y n depending on the numberterm·key n of letters " F ". yv, then the sequence /3 whose n-th. figure is <f>n{n) is computableterm·key.

If <f>n(m) is the m-th figure of We suppose that the table for Tl has been written out in such a way that in each line only one operation appears in the operations column. We also suppose that S, 0, 0, and 1 do not occur in the table, and we replace 9 throughout by 0, 0 by 0, and 1 b y l. Further substitutions are then made. Any line of form replace by and any line of the form te(23, u, h, k) re(93, t>, h, k) and we add to the table the following lines: R, Pk, R, P0, R, P0 Uj.

pe(ul5 0) u 2 re(u3, u3, k, h) pe(u2, F) and similar lines with x> for u and 1 for 0 together with the following line R, PE, R, Ph We then have the table for the machineterm·key (H/ which computes jS. The initial m-configurationterm·def is c, and the initial scanned symbolterm·key is the second a.

1936.] ON COMPUTABLE NUMBERSterm·dom.

259 11. Application to the Entscheidungsproblemterm·dom.

The results of § 8 have some important applications. In particular, they can be used to show that the Hilbert Entscheidungsproblemterm·dom 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 Grundziige 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 2( of the functional calculus K is provable, i.e. that there can be no machineterm·key which, supplied with any one 21 of these formulae, will eventually say whether 21 is provable.

It should perhaps be remarked that what I shall prove is quite different from the well-known results of Godelf. G odel has shown that (in the formalism of Principia Mathematica) there are propositions 21 such that neither '21 nor — 21 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 % is provable in K, or, what comes to the same, whether the system consisting of K with —21 adjoined as an cextra axiom is consistent.

If the negation of what Godel has shown had been proved, i.e. if, for each 21, either 21 or — 21 is provable, then we should have an immediate solution of the Entscheidungsproblemterm·dom. For we can invent a machineterm·key JC which will prove consecutively all provable formulae. Sooner or later JC will reach either 21 or —21. If it reaches 21, then we know that 2( is provable. If it reaches — 21, then, since K is consistent (Hilbert and Ackermann, p. 65), we know that 21 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 machineterm·key it we construct a formula Un (it) and we show that, if there is a general method for determining whether Un (.11) is provable, then there is a general method for determining whether it ever prints 0.

The interpretations of the propositional functions involved are as follows : Rst(x> V) is to be interpreted as "in the complete configurationterm·key x (of J/l) the symbolterm·key on the square y is S".

t Loc. cit.

260 A. M. TURINGpersName [NOV. 12, I(x, y) is to be interpreted as "in the complete configurationterm·key x the square y is scanned".

KQm(x) is to be interpreted as "in the complete configurationterm·key x the m-configurationterm·def is qm.

F(x, y) is to be interpreted as sty is the immediate successor of x ".

Inst {qt Sj 8k L 37} is to be an 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) Inst {q{ 8, Sk R qt} and Inst {qt 8j Sk N q{] are to be abbreviations for other similarly constructed expressions.

Let us put the description of .11 into the first standard form of § 6. This description consists of a numberterm·key of expressions such as "q{ 8i Sk Lqt" (or with ROT N substituted for L). Let us form all the corresponding expressions such as Inst {qt $3- Sk L qt} and take their logical sum. This we call Des(.U).

The formula Un(.U) is to 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) (30 [N(s) & N(t) & RSl(s, t)).

[K{u)&... &Des(.U)] may be abbreviated to A(M).

When we substitute the meanings suggested on p. 259-60 we find that Un(.U) has the interpretation "in some complete configurationterm·key of M, S-^ (i.e. 0) appears on the tapeterm·key ". Corresponding to this I prove that (a) If Sx appears on the tapeterm·key in some complete configurationterm·key of • U, then Un(U) is provable.

(b) If Un (• U) is provable, then 8X appears on the tapeterm·key in some complete configurationterm·key of • 11.

When this has been done, the remainder of the theorem is trivial.

1936.] ON COMPUTABLE NUMBERSterm·dom.

261 LEMMA 1.

// S ± appears on the tapeterm·key in some complete configurationterm·key of .At, then Un(.At) is provable.

We have to show how to prove Un (it). Let us suppose that in the n-th complete configurationterm·key the sequence of symbolsterm·key on the tapeterm·key is &r(n,o)> *^r(n,i)5 •••> $i<n,nh followed by nothing but blanks, and that the scanned symbolterm·key is the i(n)-th, and that the m-configurationterm·def is q^ n). Then we may form the proposition , u) & RSrluJvF>, u') & ... & RSr{H,Mn\ which we may abbreviate to CC n.

As before, F{u, u') & F{u', u") & ... & F{u^\ w(r)) is abbreviated to F<r).

I shall show that all formulae of the form A{-W) & F™^- CCn (abbreviated to CFn) are provable. The meaning of CFn is " The n-th. complete configurationterm·key of it is so and so ", where "so and so " stands for the actual n-th. complete configurationterm·key of i t. That CF n should be provable is therefore to be expected.

CF0 is certainly provable, for in the complete configurationterm·key the symbolsterm·key are all blanks, the m-configurationterm·def is q x, and the scanned square is u, i.e. CC0 is (y) RSo{u, y) & I(u, u) & KQl(u).

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

We next show that CF n^-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-j-l)-th configurationterm·key the machineterm·key moves to left or to right or remains stationary. We suppose that the first case applies, i.e. the machineterm·key moves to the left. A similar argument applies in the other cases. If r[n,i(n)}=a, r(n-\-l, i(n-\-l)} = c, k(i(n)j =b, and k(i(n-\-l)) =d, then Des (it) must include Inst {qa 8b Sd L q^ as one of its terms, i.e.

Hence But A(.AV) & Fin+n^1nat{qa8b8dLqc} & Inst{q a Sb 8dLqc} & ^ n + w^ ( C C n - is provable, and so therefore is A (• It) & F(n+»-> (CCn -» C(L ., 262 and A. M. TURINGpersName [NOV. 12, (AIM) & F™^CCn) -+ (.4(it) & F<n+V^CCn+1), i.e.

CFm-»CF.n+V CFn is provable for each n. Now it is the assumption of this lemma that 8± appears somewhere, in some complete configurationterm·key, in the sequence that is, for some integers N, K, CG N has of symbolsterm·key printed by M; u(K)) is RS[(u^N\u^) provable. We have then as one of its terms, and therefore CCN^RSl{u{N\ and We also have 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 the proof of Lemma 1.

LEMMA 2.

// Un(-U) is provable, then S1 appears on the tapeterm·key in some complete configurationterm·key 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(^U), we obtain a true proposition with the meaning " S 1 appears somewhere on the tapeterm·key in some complete configurationterm·key of .M".

Let us suppose the contrary.

We are now in a position to show that the Entscheidungsproblemterm·dom cannot Then there is a general be solved. (mechanical) process for determining whether Un(.tl) is provable. By Lemmas 1 and 2, this implies that there is a process for determining whether .41 ever prints 0, and this is impossible, by §8. Hence the Entscheidungsproblemterm·dom cannot be solved.

In view of the large numberterm·key of particular cases of solutions of the Entscheidungsproblemterm·dom for formulae with restricted systems of quantors, it 1936.] ON COMPUTABLE NUMBERSterm·dom.

263 is interesting to express Un(ii) in a form in which all quantors are at the beginning. Un(At) is, in fact, expressible in the form {u){3x){w){3u1)...{3un)%, (I) where 95 contains no quantors, and n = 6. By unimportant modifications we can obtain a formula, with all essential properties of Un(.it), which is of form (I) with n = 5.

Added 28 August, 1936.

APPENDIX.

Computabiliiy and effective calculabilityterm·dom The theorem that all effectively calculable (A-definable) sequences are It is assumed, computableterm·key and its converse are proved below in outline. 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 N n. We shall say that 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 there is a W.F.F. My such that, for all integers n, i.e. {My} (Nn) is convertible into Xxy.x(x(y)) or into Xxy.x(y) according as the n-th figure of A is 1 or 0.

To show that every A-definable sequence y is computableterm·key, we have to show how to construct a machineterm·key to compute y. For use with machinesterm·key it is convenient to make a trivial modification in the calculus of conversion. ... as variables instead of This alteration consists in using x, x', x", a, b, c, .... We now construct a machineterm·key JL which, when supplied with the formula My, writes down the sequence y. The construction of X is somewhat similar to that of the machineterm·key K which proves all provable formulae of the functional calculus. We first construct a choice machineterm·key £-v which, if supplied with a W.F.F., M say, and suitably manipulated, obtains any formula into which M is convertible. £± can then be modified so as to yield an automatic machineterm·key £-2 which obtains successively all the formulae 264 A. M. TURINGpersName [NOV. 12, into which M is convertible (cf. foot-note p. 252). The machineterm·key £> as a P a r^. The motion of the machineterm·key X when supplied includes ^ 2 with the formula My is divided into sections of which the n-th. is devoted to finding the n-th figure of y. The first stage in this n-th. section is the formation of {My} {Nn). This formula is then supplied to the machineterm·key £2, 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 and with Aa:|Aa;'[{a;}(a;')] |, i.e. Nv If it is identical with the first of these, then the machineterm·key 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 .!!2 is resumed. By hypothesis, {My}(Nn) is convertible into one of the formulae N2 or Nx; consequently the n-th section will eventually be finished, i.e. the n-th. figure of y will eventually be written down.

To prove that every computableterm·key sequence y is A-defUiable, we must show how to find a formula My such that, for all integers n, {My}(Nn)c(mvN1+<j)y{n).

Let .11 be a machineterm·key which computes y and let us take some description of the complete configurationsterm·key of -U by means of numbersterm·key, e.g. we may take the D.N of the complete configurationterm·key as described in §6. Let £(n) be the D.N of the w-th complete configurationterm·key of M. The table for the machineterm·key ..U gives us a relation between £(n-\-l) and £(n) of the form where py is a function of very restricted, although not usually very simple, form : it is determined by the table for. U. py is A-defmable (I omit the proof of this), i.e. there is a W.F.F. A y such that, for all integers n, Let U stand for Xu[{{u}(Ay))(Nr)], where r=£(0); then, for all integers n, {Uy}(NJ conv N,{n).

1936.] ON COMPUTABLE NUMBERSterm·dom.

265 It may be proved that there is a formula V such that conv Nx if, in going from the n-th to the (n-\- l)-th complete configurationterm·key, the figure 0 is printed.

conv JV2 if the figure 1 is printed, conv N3 otherwise.

Let Wy stand for so that, for each integer n, conv {Wy} (Nn), and let Q be a formula such that \{Q}(Wy)UNs) convNr(s), where r(s) is the 5-th integer q for which {Wy} (NQ) is convertible into either N-L or JVa. Then, if j|f7 stands for it will have the required property f.

The Graduate College, Princeton University, New Jersey, U.S.A.

t In a complete proof of the A-definability of computableterm·key sequences it would be best to modify this method by replacing the numerical description of the complete configurationsterm·key by a description which can be handled more easily with our apparatus. Let us choose certain integers to represent the symbolsterm·key and the m-configurationsterm·def of the machineterm·key. Suppose that in a certain complete configurationterm·key the numbersterm·key representing the successive symbolsterm·key on the tapeterm·key are s1s2... sn, that the m-th symbolterm·key is scanned, and that the ?n.-configurationhas the numberterm·key t; then we may represent this complete configurationterm·key by the formula „ N» ..., #,„,_,], [Nt, NaJ, [NSM+V ..., NSlt]], [a, 6] stands for \u f" -{ {u} (a) )(&)]» [a, 6, c] stands for AM P I \ {u} (a)}(b) J (c)l, where etc.