A.M. TURING,

[NOV. 12,

 ON COMPUTABLE THE NUMBERS, WITH AN APPLICATION 
    TO THE ENTSHIEDINGS PROBLEM

                                  By A. M.TURING 

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



P230

The "computable" numbers may be described briefly as the reaI
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 fimctions
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 aceomit 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 1 give some arguments with the intention of showing that the
computable numbers include all numbers wlfich 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 ,r, 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
ways similar to the class of real numbers, it is nevertheless enumerable.
In §8 Iexamine 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 *Godel. These results

________________________________________________________________________________
* Godel, "Uber formal unentscheidbare Satze der Principia Mathematica und ver-
wandter Systeme, I", Monatshefte Math. Phys., 38 (1931), 173-198.
________________________________________________________________________________


P231

have valuable applications. In particular, it is shown (§ 11) that the
Hilbertian Entscheidungsproblem can have no solution.
In a recent paper *Alonzo Church has introduce[1 an idea of "effectiv
calculability", which is equivalent to my "computability", but is very
differently defined. Church also reaches similar conclusions about the
**Entscheidungsproblem:. 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 prcsent 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 a
machine which is only capable of a finite number of conditions q1, q2, ..., ql:
which will be called "m-configurations" The machine is supplied with a
"tape" (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 G(r)
which is "in the machine" We may call this square the "scannedsquare ".
 The symbol on the scanned square may be called the "scannedsymbol ".
 The "scanned symbol" is the only one of which the machine
is, so to speak, "directly aware". However, by altering its m-configuration
 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 m-configuration qn and the
scanned symbol G(r). This pair qn,G(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
_________________________________________________________________________________
* Alonzo Church, "An unsolvable problem of elementary nmnber theory", American
J. of Math., 58 (1936), 345-363.
** Alonzo Church, "A note on the Entscheidungsproblem", J. of ,Symbolic Logic, l
(1936), 40-41.
_________________________________________________________________________________

P232

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.

                    2. Definitions.

                    Automatic machines.

 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 all 
"automatic machine" (or a-machine).
For some purposes we might use machines (choice machines orc-machines)
 whose motion is only 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 m-configuration, the subsequence of the symbols
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
m-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.
_________________________________________________________________________________

P233

                    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", "p", "e"
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 apphes for ally symbol and for no symbol. The machine
starts in the m-configuration "b" with a blank tape.


以上３章まで