By A. M. TURING.[Received 28 May, 1936.—Read 12 November, 1936.]
The “computable” numbers may be described briefly as the realnumbers 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 functionsof an integral variable or a real or computable variable, computablepredicates, and so forth. The fundamental problems involved are,however, the same in each case, and I have chosen the computable numbersfor explicit treatment as involving the least cumbrous technique. I hopeshortly to give an account of the relations of the computable numbers,functions, and so forth to one another. This will include a developmentof the theory of functions of a real variable expressed in terms of com-putable numbers. According to my definition, a number is computableif its decimal can be written down by a machine.In §§ 9, 10 I give some arguments with the intention of showing that thecomputable numbers include all numbers which could naturally beregarded as computable. In particular, I show that certain large classesof numbers are computable. They include, for instance, the real parts ofall algebraic numbers, the real parts of the zeros of the Bessel functions,the numbers IT, e, etc. The computable numbers do not, however, includeall definable numbers, and an example is given of a definable numberwhich is not computable.Although the class of computable numbers is so great, and in manyAvays 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 arereached which are superficially similar to those of Gbdelf. These resultsf Godel, ” Uber formal unentscheidbare Satze der Principia Mathematica und ver-•vvandter Systeme, I”. Monatsheftc Math. Phys., 38 (1931), 173-198.1936.] ON COMPUTABLE NUMBERS. 231have valuable applications. In particular, it is shown (§11) that theHilbertian Entscheidungsproblem can have no solution.In a recent paper Alonzo Church f has introduced an idea of “effectivecalculability”, which is equivalent to my “computability”, but is verydifferently defined. Church also reaches similar conclusions about theEntscheidungsproblemJ. The proof of equivalence between “computa-bility” and “effective calculability” is outlined in an appendix to thepresent paper.1. Computing machines.We have said that the computable numbers are those whose decimalsare calculable by finite means. This requires rather more explicitdefinition. No real attempt will be made to justify the definitions givenuntil we reach § 9. For the present I shall only say that the justificationlies in the fact that the human memory is necessarily limited.We may compare a man in the process of computing a real number to ;imachine 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”tape” (the analogue of paper) running through it, and divided intosections (called “squares”) each capable of bearing a “symbol”. Atany 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 “scannedsquare “. The symbol on the scanned square may be called the ” scannedsymbol”. The “scanned symbol” is the only one of which the machineis, so to speak, “directly aware”. However, by altering its m-configu-ration the machine can effectively remember some of the symbols whichit has “seen” (scanned) previously. The possible behaviour of themachine at any moment is determined by the ra-configuration qn and thescanned 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 scannedsquare: in other configurations it erases the scanned symbol. Themachine may also change the square which is being scanned, but only byshifting it one place to right or left. In addition to any of these operationsthe m-configuration may be changed. Some of the symbols written downf Alonzo Church, ” An unsolvable problem, of elementary number theory “, AmericanJ. of Math., 58 (1936), 345-363.X Alonzo Church, “A note on the Entscheidungsproblem”, J. of Symbolic Logic, 1(1936), 40-41.