EXHIBIT 1014
`
`
`
`TO PETITIONER GOOGLE INC.’S
`PETITION FOR COVERED BUSINESS
`METHOD REVIEW OF
`U.S. PATENT NO. 8,794,516
`
`
`
`
`
`
`
`

`
`230
`
`A. M. TUKING
`
`[Nov.
`
`12,
`
`ON COMPUTABLE NUMBERS, WITH AN APPLICATION TO
`THE ENTSCHEIDUNGSPROBLEM
`
`By A. M. TURING.
`
`[Received 28 May, 1936.—Read 12 November, 1936.]
`
`The "computable" numbers may be described briefly as the real
`numbers whose expressions as a decimal are calculable by finite means.
`Although the subject of this paper is ostensibly the computable numbers.
`it is almost equally easy to 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, the same in each case, and I have chosen the computable numbers
`for explicit treatment as involving the least cumbrous technique.
`I hope
`shortly to give an account of the relations of the computable numbers,
`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 com-
`putable numbers. According to my definition, a number is computable
`if its decimal can be written down by a machine.
`In §§ 9, 10 I give some arguments with the intention of showing that the
`computable numbers include all numbers which could naturally be
`regarded as computable.
`In particular, I show that certain large classes
`of numbers are computable. They include, for instance, the real parts of
`all algebraic numbers, the real parts of the zeros of the Bessel functions,
`the numbers IT, e, etc. The computable numbers do not, however, include
`all definable numbers, and an example is given of a definable number
`which is not computable.
`Although the class of computable numbers is so great, and in many
`Avays similar to the class of real numbers, 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.
`
`Google Exhibit 1014 Page 00001
`
`

`
`1936.]
`
`ON COMPUTABLE NUMBERS.
`
`231
`
`In particular, it is shown (§11) that the
`have valuable applications.
`Hilbertian Entscheidungsproblem can have no solution.
`In 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 about the
`EntscheidungsproblemJ. The proof of equivalence between "computa-
`bility" and "effective calculability" is outlined in an appendix to the
`present paper.
`
`1. Computing machines.
`
`We have said that the computable numbers are those whose decimals
`are calculable by finite 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 number to ;i
`machine which is only capable of a finite number of conditions q1: q2. .... qI;
`which will be called " m-configurations ". The machine 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 "symbol". At
`any moment there is just one square, say the r-th, bearing the symbol <2>(r)
`which is "in the machine". We may call this square the "scanned
`square ". The symbol on the scanned square may be called the " scanned
`symbol". The "scanned symbol" is the only one of which the machine
`is, so to speak, "directly aware". However, by altering its m-configu-
`ration the machine can effectively remember some of the symbols which
`it has "seen" (scanned) previously. The possible behaviour of the
`machine at any moment is determined by the ra-configuration q n and the
`scanned symbol <S (r). This pair qn, © (r) will be called the '' configuration'':
`thus the configuration determines the possible behaviour of the machine.
`In some of the configurations in which the scanned square is blank (i.e.
`bears no symbol) the machine writes down a new symbol on the scanned
`square:
`in other configurations it erases the scanned symbol. The
`machine 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-configuration may be changed. Some of the symbols written 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.
`
`Page 00002
`
`

`
`232
`
`A. M. TURING
`
`[Nov. 12,
`
`will form the sequence of figures which is the decimal of the real number
`which is being computed. The others are just rough notes to "assist the
`memory ".
`It will only be these rough notes which will be liable to erasure.
`It is my contention that these operations include all those which are used
`in the computation of a number. The defence of this contention will be
`easier when the theory of the machines 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 "machine", "tape",
`"scanned", etc.
`
`Automatic machines.
`
`2. Definitions.
`
`If at each stage the motion of a machine (in the sense of § 1) is completely
`determined by the configuration, we shall call the machine an "auto-
`matic machine" (or a-machine).
`.For some purposes we might use machines (choice machines or
`c-manhines) whose motion is onty partially determined by the configuration
`(hence the use of the word "possible" in §1). When such a machine
`reaches one of these ambiguous configurations, it cannot go on until some
`arbitrary choice has been made by an external operator. This would be the
`case if we were using machines to deal with axiomatic systems. In this
`paper I deal only with automatic machines, and will therefore often omit
`the prefix a-.
`
`Computing machines.
`
`If an a-machine prints two kinds of symbols, of which the first kind
`(called figures) consists entirely of 0 and 1 (the others being called symbols of
`the second kind), then the machine will be called a computing machine.
`If the machine is supplied with a blank tape 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 machine. The real number whose expression as a binary decimal is
`obtained by prefacing this sequence by a decimal point is called the
`number computed by the machine.
`At any stage of the motion of the machine, the number of the scanned
`square, the complete sequence of all symbols on the tape, and the
`ra-configuration will be said to describe the complete configuration at that
`stage. The changes of the machine and tape between successive complete
`configurations will be called the moves of the machine.
`
`Page 00003
`
`

`
`1936.]
`
`ON COMPUTABLE NUMBERS.
`
`233
`
`Circular and circle-free machines.
`
`If a computing machine never writes down more than a finite number
`of symbols of the first kind, it will be called circular. Otherwise it is said to
`be circle-free.
`A machine will be circular if it reaches a configuration from which there
`is no possible move, or if it goes on moving, and possibly printing symbols
`of the second kind, but cannot print any more symbols of the first kind.
`The significance of the term "circular" will be explained in §8.
`
`Computable sequences and numbers.
`
`A sequence is said to be computable if it can be computed by a circle-free
`machine. A number is computable if it differs by an integer from the
`number computed by a circle-free machine.
`We shall avoid confusion by speaking more often of computable
`sequences than of computable numbers.
`
`3. Examples of computing machines.
`
`I. A machine can be constructed to compute the sequence 010101....
`The machine is to have the four m-configurations " b ", " c ", "£", "c :>
`and is capable of printing " 0 " and " 1 ". The behaviour of the machine is
`described in the following table in which " R " means "the machine 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
`symbol 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 configuration described in the first two columns the operations in the
`third column are carried out successively, and the machine then goes over
`into the m-configuration 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 symbol and for no symbol. The machine
`starts in the m-configuration b with a blank tape.
`
`-config.
`
`c c t b
`
`Configuration
`m-config.
`symbol
`None
`
`Behaviour
`operations
`final
`PO, R
`
`None
`None
`
`None
`
`R
`PI, R
`
`R
`
`b c c I
`
`Page 00004
`
`

`
`234
`
`A. M. TURING
`
`[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.
`
`operations
`
`final m-config.
`
`6 b b
`
`PO
`
`R, R, PI
`
`R, R, PO
`
`symbol
`
`None
`
`0 1
`
`m-config.
`
`II. As a slightly more difficult example we can construct a machine to
`compute the sequence 001011011101111011111
`The machine is to
`be capable of five ra-configurations, viz. " o ", " q ", "p ", " f ", " b " and of
`printing " o ", "x", " 0 ", " 1 ". The first three symbols on the tape will
`be " aoO " ; the other figures follow on alternate squares. On the inter-
`mediate 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.
`
`Configuration
`m-config.
`symbol
`
`Behaviour
`operations
`
`final
`m-config.
`
`0 0 q q p q f p f 0
`
`b
`
`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
`
`PI, L
`
`E, R
`
`R
`
`L, L
`
`R,R
`
`PO, L, L
`
`To illustrate the working of this machine a table is given below of the
`first few complete configurations. These complete configurations are
`described by writing down the sequence of symbols which are on the tape,
`
`Page 00005
`
`

`
`1936.]
`
`ON COMPUTABLE NUMBERS.
`
`with the m-configuration written below the scanned symbol.
`successive complete configurations are separated by colons.
`
`235
`
`The
`
`O r o oO
`
`9 90
`
`0 : 9 90
`: 9 90
`q
`o
`b
`1 : 9 90 0
`9 90 0
`P
`P
`0 1 : 9 90 0 1
`f
`9 9 0 0 H - 0: ....
`
` 0
`
`: 9 90 0 1:
`0 : 9 90
`q
`q
`p
`1 : 9 90 0 1 : 9 90 0 1:
`f
`f
`: o a0 0 1 0:
`f
`
`c
`
`This table could also be written in the form
`
`(C)
`b :9 9 o 0 0 : 9 9 q 0 0 : ...,
`in which a space has been made on the left of the scanned symbol and the*
`m-configuration 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 alter-
`nate squares JF'-squares and the other sequence ^/-squares. The symbols oi •.
`^-squares will be liable to erasure. The symbols 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
`rich variety of symbols capable of being printed on ^-squares.
`If a
`symbol /3 is on an F-square S and a symbol 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 machines, and.
`these, in some machines, are used in many connections. These processes
`include copying down sequences of symbols, comparing sequences, erasing
`all symbols of a given form, etc. Where such processes are concerned we
`can abbreviate the tables for the m-configurations considerably by the use
`of "skeleton tables".
`In skeleton tables there appear capital German
`letters and small Greek letters. These are of the nature of "variables '".
`By replacing each capital German letter throughout by an ^^-configuration
`
`Page 00006
`
`

`
`236
`
`A. M. TURING
`
`[Nov. 12,
`
`and each small Greek letter by a symbol, we obtain the table for an
`m-configuration.
`The skeleton tables are to be regarded as nothing but abbreviations:
`they are not essential. So long as the reader understands how to obtain
`the complete tables from the skeleton tables, there is no need to give any
`exact definitions in this connection.
`Let us consider an example:
`
`m-config.
`
`Symbol Behaviour
`
`Final
`m-config.
`
`the m-configuration
`From
`f(@, 93, a) the machine finds the
`symbol of form a which is far-
`thest to the left (the "first a")
`and
`the ?w-confi,guration
`then
`becomes (L
`If there is no a
`then
`the m-configuration be-
`comes 93.
`
`f^G, 95, a)
`
`f(<5,S3,a)
`
`f2(G,
`
`I, 93, a)
`
`L
`
`L
`
`R R
`
`R
`
`f a
`
`not a
`
`f(e,S5,a)
`
`fi(6,93,a)
`
`None
`R
`93
`If we were to replace £ throughout by q (say), 93 by r, and a. by x, we
`should have a complete table for the m-configuration f (q, x, x).
`f is called
`an "?/i-configuration function" or "m-function".
`The only expressions which are admissible for substitution in an
`»i-function are the m-configurations and symbols of the machine. 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 machine had certain m-configurations (enumerated) and all m-configu-
`rations obtainable by substitution of m-configurations in certain m-func-
`tion.-J, we .should usually get an infinity of m-configurations; e.g., we might
`say that the machine was to have the m-configuration q and all m-configu-
`rations obtainable by substituting an m-configuration 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 machine, mostly expressed in terms of m-functions.
`We are also given skeleton tables. All we want is the complete table for
`the m-configurations of the machine. This is obtained by repeated
`substitution in the skeleton tables.
`
`Page 00007
`
`

`
`1936.]
`
`ON COMPUTABLE NUMBERS.
`
`237
`
`Further examples.
`
`(In the explanations the symbol " - >" is used to signify "the machine
`goes into the ra-configuration. . . . ")
`
`e((5,23,a)
`
`„
`c^G, S3, a) #
`
`f (e^S, S3, a), S3, a)
`^
`G
`
`c(S3, a)
`
`c(c(S3, a), 23, a)
`
`From c(S, 23, a) the first a is
`erased and -> (L
`If there is no
`
`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-configurations of some machine
`there appears c('b, x) ( = q, saj'). The table is
`
`or
`
`c(6; a;)
`
`q
`
`Or, in greater detail:
`
`e(c(b, x). h, x)
`
`c(q, 6, a;).
`
`q
`
`c(q, 6, x)
`
`c(q, 6, x)
`
`f (ci(q, 6, a.1), t), a)
`
`Cj.(q, I), re)
`
`£•
`
`q.
`
`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 machine
`
`[Any
`ue (<S j8) \
`[None P/S
`
`i?3JR
`
`^
`j^
`
`I(S)
`r/gx
`
`f ( 6 , » , o)
`
`f"(S,»,o)
`
`pe^S.jS)
`
`P r i n ts ^ ^
`^
`sequence of sj^mbols and -> C
`
`6
`
`2
`G
`
`f(t(6),a3,a)
`
`f(t(S),S8,a)
`
`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)
`
`R
`
`f'(c-i(S), 55, a)
`pe(€
` JS)
`
`c(<£, S3, a). The machine
`writes at the end the first sym-
`bol marked a and -> £.
`
`Page 00008
`
`

`
`238
`
`A. M. TURING
`
`[NOV. 12,
`
`The last line stands for the totality of lines obtainable from it by
`replacing fi by any symbol which may occur on the tape of the machine
`concerned.
`
`cc(£,S3,a)
`
`c(e(G,S3,a),83,a)
`
`cc(23,a)
`
`ce(ce(83,a),23,a)
`
`ce(23, a). The machine
`copies down in order at the
`end all symbols marked a
`and erases the letters a; ->SS.
`
`vc(G,93,a,j8)
`
`re^^a.fl E,Pp
`
`re(S, a, P)
`
`cr(Ci,23;a)
`
`f(re1(g3$B3a,i8),^5a)
`
`rc(£, S3, a, 0). The ma-
`chine replaces the first a by
`(8 a n d - > g^ 35 if there is no a.
`<Z
`re («(», a, j8), 93, a, j8) «<»' 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-configuration cv(5S, a)
`is
`taken up when no letters
`" a" are on the tape.
`
`c(tt(G,9$,a,a), S3,a)
`
`«(«(5S,a),rc(SS,a,a),a)
`
`•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)
`
`7
`
`7
`
`f (cp2(e,2T, y), S(,
`
`S
`
`SI.
`[noty
`If
`The first symbol marked a and the first marked ]8 are compared.
`If there are both and the symbols 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 symbols marked a is compared with
`the sequence marked /?. -> Q if they are similar. Otherwise -> 21. Some
`of the symbols a and /? are erased.
`
`Page 00009
`
`

`
`1936.]
`
`ON COMPUTABLE NUMBERS.
`
`239
`
`a). The machine
`the
`last symbol of
`finds
`form a.
`-> @.
`
`3)> a )
`
`pc2(S, a, jS). The machine
`prints a j8 at the end.
`
`ce(ce(255j8), a)
`
`ce3(S5,a,j8,y). The mach-
`ine copies down at the end
`ce (ce2(S5,0, y), a) £ r st the symbols marked a,
`then those marked jS, and
`finally those marked y;
`it
`erases the symbols a, /?, y.
`
`e1((5)
`,^>
`
`From e(^) the marks are
`erased from all marked sym-
`bols.
`-> @.
`
`R R R
`
`JAny
`[None
`JAny
`[None
`
`not a
`
`ce2(95, a,
`
`ce3(S5,a,
`
`j8,y)
`
`R L
`
`f Any R, E, R
`None
`
`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.
`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 intro-
`ducing more m-configurations. Now let us give numbers to the w-configu-
`rations, 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
`
`Page 00010
`
`

`
`240
`
`A. M. TUBING
`
`[Nov. 12,
`
`and, in particular, blank = 80, 0 = Slt 1 = S2. The hnes of the table are
`now of form
`
`Symbol
`s,
`
`m-config.
`
`to
`to
`to
`
`Si
`
`Si
`
`Si
`
`Si
`
`Si
`
`Lines such as
`
`to
`are to be written as
`
`to
`and lines such as
`
`ft
`
`to be written as
`
`Operations
`
`Final
`m-config.
`
`PSk,L
`PSkiR
`
`PSk
`
`E, R
`
`PS0, R
`
`R
`
`PS,, R
`
`s.
`to
`In this way we reduce each line of the table to a line of one of the forms
`(Nj, (N2), (i\y.
`let us form an expression q( Sj]Sb L qm;
`From each line of form (N^
`(N2) we form an expression
`from each
`line of form
`qiSjSkRqm;
`and from each line of form (N3) we form an expression #,•#, SkNqm.
`Let us write down all expressions so formed from the table for the
`machine and separate them by semi-colons.
`In this way we obtain a
`complete description of the machine.
`In this description we shall replace
`q{ by the letter "D" followed by the letter "A" repeated i times, and $,- by
`" D" followed by "C"
`repeated j times. This new description of the
`machine may be called the standard description (S.D).
`It is made up
`entirely from the letters "A", " C", "D", "L", "R", "N", and from
`
`If finally we replace "A" by " 1 ", "C" by " 2 ", "D" by " 3 ", " L"
`by " 4 ", "R" by c ' 5 ", "N" by " 6 ", and "* 3> by £ <7" we sh,all have a
`description of the machine in the form of an arabic numeral. The integer
`represented by this numeral may be called a description number (D.N) of
`the machine. The D.N determine the S.D and the structure of the
`
`Page 00011
`
`

`
`1936.]
`
`ON COMPUTABLE NUMBERS.
`
`241
`
`machine uniquely. The machine whose D.N is n may be described as
`
`To each computable sequence there corresponds at least one description
`number, while to no description number does there correspond more than
`one computable sequence. The computable sequences and numbers are
`therefore enumerable.
`Let us find a description number for the machine I of § 3. When we
`rename the m-configurations its table becomes:
`
`q-L
`
`q2
`
`q3
`
`ft
`
`^o
`
`SQ
`
`So
`
`
`
`SQ
`
`*b 1} K
`
`P8O, R
`
`PS2) R
`
`PSo>R
`
`q2
`
`q3
`
`#4
`
`ft
`
`Other tables could be obtained by adding irrelevant lines such as
`
`qx
`
`Sx
`
`PSVR
`
`q2
`
`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 number is
`
`31332531173113353111731113322531111731111335317
`
`and so is
`3133253117311335311173111332253111173111133531731323253117
`
`A number which is a description number of a circle-free machine will be
`In § 8 it is shown that there can be no general
`called a satisfactory number.
`process for determining whether a given number is satisfactory or not.
`
`6. The universal computing machine.
`
`It is possible to invent a single machine which can be used to compute
`any computable sequence. If this machine M is supplied with a tape on
`the beginning of which is written the S.D of some computing machine .At,
`8KR. 2. VOL. 42. NO. 2144.
`B
`
`Page 00012
`
`

`
`242
`
`A. M. TURING
`
`[NOV. 12,
`
`In this section I explain
`then 'It will compute the same sequence as it.
`in outline the behaviour of the machine. The next section is devoted to
`giving the complete table for U.
`Let us first suppose that we have a machine i t' which will write down on
`the .F-squares the successive complete configurations of i t. These might
`be expressed in the same form as on p. 235, using the second description,
`(C), with all symbols on one line. Or, better, we could transform this
`description (as in §5) by replacing each ra-configuration by " D" followed
`by "A" repeated the appropriate number of times, and by replacing each
`symbol by " D" followed by "C"
`repeated the appropriate number of
`times. The numbers of letters'' A " and'' C " are to agree with the numbers
`chosen in §5, so that, in particular, " 0" is replaced by "DC",
`" 1" by
`"DCC", and the blanks by " D ". These substitutions are to be made
`after the complete configurations have been put together, as in (C). Diffi-
`culties arise if we do the substitution first. In each complete configura-
`tion the blanks would all have to be replaced by " D ", so that the complete
`configuration would not be expressed as a finite sequence of symbols.
`If in the description of the machine II of § 3 we replace " o " by " DA A ",
`" a" by "DCCC", " q" by "DAAA",
`then the sequence (C) becomes:
`
`DA .DCCCDCCCDAADCDDC.DCCCDCCCDAAADCDDC:... (CJ
`
`(This is the sequence of symbols on ^-squares.)
`It is not difficult to see that if it can be constructed, then so can it'.
`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
`il/); 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 ex-
`changed for others and we have something very akin to the universal
`machine.
`One thing is lacking : at present the machine i t' prints no figures. We
`may correct this by printing between each successive pair of complete
`configurations the figures which appear in the new configuration but not
`in the old. Then (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 configurations.
`When the letters are replaced by figures, as in § 5, we shall have a numerical
`
`Page 00013
`
`

`
`1936.]
`
`ON COMPUTABLE NUMBERS.
`
`243
`
`•description of the complete configuration, which may be called its descrip-
`tion number.
`
`7. Detailed description of the universal machine.
`
`A table is given below of the behaviour of this universal machine. The
`•m-configurations of which the machine is capable are all those occurring in
`the first and last columns of the table, together with all those which occur
`when we write out the unabbreviated tables of those which appear in the
`table in the form of m-functions. E.g., e(anf) appears in the table and is an
`wi-fimction.
`Its unabbreviated table is (see p. 239)
`
`e^onf)
`c(anf)
`
`ei(anf)
`anf
`
`R L
`
`R, E, R
`
`ot 9
`
`9 n
`
`Any
`
`None
`
`e(anf)
`
`e^anf)
`
`Consequently e1(anf) is an m-configuration of U.
`When \l is ready to start work the tape running through it bears on it
`the symbol 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 machine followed by a double
`colon " : :" (a single symbol, on an .F-square). The S.D consists of a
`number of instructions, separated by semi-colons.
`Each instruction consists of five consecutive parts
`
`(i) " D" followed by a sequence of letters "A".
`relevant m-configuration.
`
`This describes the
`
`(ii) "JD" followed by a sequence of letters " C". This describes the
`scanned symbol.
`
`(iii) " D" followed by another sequence of letters "C".
`describes the symbol into which the scanned symbol is to be changed.
`
`This
`
`(iv) "L ", " i 2 ", or "JV", describing whether the machine is to move
`to left, right, or not at all.
`
`(v) " D" followed by a sequence of letters "A".
`final m-configuration.
`
`This describes the
`
`" 0 ", c t D ", " 0 ",
`The machine U is to be capable of printing "A",
`• " 1 ", "u", "v", "w", " z ", "y", " z ". The S.D is formed from " ; ",
`
`((R"}
`"C",
`" D ", " L ",
`•"A",
`"N".
`
`Page 00014
`
`

`
`244
`
`A. M. TURING
`
`[Nov. 12,
`
`Subsidiary skeleton table.
`
`L, Pa, R con^S, a)
`R,Pa,R
`c o n ^ a)
`
`R, R
`
`con(£, a)
`
`con(@. a). Starting from
`an J^-square, S say, the se-
`q u e n ce Q of s y m b o ls de scrib-
`ing a configuration closest on
`the right of S is marked out
`->@.
`R, Pa, R con2(§, a) with letters a.
`
`(Not A
`
`A
`A
`
`D G
`
`con(@, a)
`
`con^CE, a)
`
`con2(§, a)
`
`R, Pa, R con2(£,a)
`
`Not C
`
`R.R
`
`con(S, ). In the final con-
`figuration
`the machine
`is
`scanning the square which is
`four squares to the right of the
`last square of C. C is left
`unmarked.
`
`6. The machine prints
`on the .F-squares after
`->anf.
`
`anf. The machine marks
`the configuration in the last
`c o m p i e te configuration with
`y.
`-
`
`font. The machine finds
`last
`semi-colon not
`the
`marked with z.
`It marks
`this semi-colon with z and
`the configuration
`following
`it with x.
`
`fmp. The machine com-
`pares the sequences marked
`x and y.
`It erases all letters
`x and y. -> Sim if they are
`alike. Otherwise ->• font.
`
`The table for U.
`
`hx R,R,P:,R,R,PD;R,R,PA
`
`anf
`
`anf
`
`font
`
`g(anf1} :)
`
`COn (font, y)
`
`con (limp, x)
`
`!om
`
`!om
`
`R, Pz: L
`L,L
`
`not z nor
`
`L
`
`Hnr,>
`
`cpe(c(fom, x, y), iim, x, y)
`
`anf. Taking the long view, the last instruction relevant to the last
`configuration is found.
`It can be recognised afterwards as the instruction
`following the last semi-colon marked z.
`-Mim.
`
`Page 00015
`
`

`
`1936.]
`
`Sim
`
`ON COMPUTABLE NUMBERS.
`
`245
`
`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 m-
`configuration with y. The let-
`ters z are erased.
`
`mi. The last complete con-
`figuration is marked out into
`four sections. The configiira-
`ration is left unmarked. The
`symbol directly preceding it is
`marked with x. The remainder
`of the complete configuration
`is divided into two parts, of
`which the first is marked with
`v and the last with w. A colon is
`printed after the whole. -> $f;.
`
`con
`
`(stm2,
`
`)
`
`Sim
`
`Sim
`
`3 2
`
`A
`
`not
`
`
`
`A .R,Pu,
`
`R, R
`
`,R
`
`not
`
`A
`
`L,
`
`Py
`
`e(mB,
`
`A
`
`L,Py,
`
`,R
`
`Sim
`3
`
`mf2
`
`L, L, L, L
`
`, Pa;, j ^, Z',
`
`A C
`
`D
`
`R, Px, L, L, L m?3
`not : R, Pv, L, L, L m!3
`:
`mL
`
`[Any
`[ None
`
`con
`
`P:
`
`mf6
`
`•mt
`
`m?3
`
`m?4
`
`mh
`
`L, L, L
`
`?, R, R, R
`
`, 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.
`
`•R, 22
`
`inSt, 0, :
`
`xnit
`
`Page 00016
`
`

`
`246
`
`in«t
`
`L)
`
`i?)
`
`\nitx{N)
`
`co
`
`A. M. TURING
`
`[NOV. 12,
`
`T he
`
`n e xt
`«**•
`complete
`configuration is written down,.
`carrying out the marked instruc-
`t i o n s - T he l e t t e rs u> v> w> x> V
`are erased.
`-^anf.
`
`fl(t(in«1),tt)
`
`a
`
`in^t1(a)
`R, E
`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 numbers
`are not enumerable would also prove that the computable numbers and
`sequences cannot be enumerable*.
`It might, for instance, be thought
`that the limit of a sequence of computable numbers must be computable.
`This is clearly only true if the sequence of computable numbers is defined
`by some rule.
`Or we might apply the diagonal process. "If the computable sequences
`are enumerable, let a/( be the n-th computable 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 computable, there exists a number 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 computable sequences are therefore not
`enumerable".
`The fallacy in this argument lies in the assumption that § is computable.
`It would be true if we could enumerate the computable sequences by finite
`means, but the problem of enumerating computable sequences is equivalent
`to the problem of finding out whether a given number is the D.N of a
`circle-free machine, and we have no general process for doing this in a finite
`number of steps.
`In fact, by applying the diagonal process argument
`correctly, we can show that there cannot be any such general process.
`The simplest and most direct proof of this is by showing that, if this
`general process exists, then there is a machine which computes /?. This
`proof, although perfectly sound, has the disadvantage that it may leave
`the reader with a feeling that "there must be something wrong". The
`proof which I shall give has not this disadvantage, and gives a certain
`insight into the significance of the idea "circle-free".
`It depends not on
`constructing /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.
`
`Page 00017
`
`

`
`1936.]
`
`ON COMPUTABLE NUMBERS.
`
`247
`
`Let us suppose that there is such a process; that is to say, that we can
`invent a machine <D- which, when supplied with the S.D of any computing
`machine il will test this S.D and if il is circular will mark the S.D with the
`symbol "u" and if it is circle-free will mark it with " s ". By combining
`the machines <& and U we could construct a machine :l I- to compute the
`sequence j8'. The machine <O- may require a tape. We may suppose that
`it uses the jE'-squares beyond all symbols on .F-squares, and that when it
`has reached its verdict all the rough work done by l0- is erased.
`In the first N— 1
`The machine Ji has its motion divided into sections.
`sections, among other things, the integers 1, 2,..., N— 1 have been written
`down and tested by the machine <Q>-. A certain number, say R(N— I), of
`them have been found to be the D.N's of circle-free machines.
`In the N-th
`section the machine (& tests the number N.
`If N is satisfactory, i.e., if it
`is the D.N of a circle-free machine, 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 machine goes on to the (iV-(-l)-t