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. 以上３章まで

トップページに戻る

チューリングさんのページへ

訳文を読みたい

チューリング機械の解説

チューリング機械の操作

チューリング機械の操作説明