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 computable 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 $\pi, 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 I 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 Gödel†. These results

† Gödel, "Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I", Monatshefte Math. Phys., 38 (1931), 173–198.

have valuable applications. In particular, it is shown (§11) that the Hilbertian Entscheidungsproblem can have no solution.

In a recent paper Alonzo Church† 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 Entscheidungsproblem‡. The proof of equivalence between "computability" and "effective calculability" is outlined in an appendix to the present paper.

計算可能数について――決定問題への応用

A. M. Turing 著。

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

「計算可能な」数とは、十進数としての表現が有限の手段によって計算可能である実数、と簡潔に記述することができる。本論文の主題は表向きには計算可能数であるが、整数変数、実変数または計算可能変数の計算可能な関数、計算可能な述語などを定義し研究することも、ほぼ同じ程度に容易である。しかし、そこに含まれる基本的な問題は、いずれの場合にも同じであり、最も煩雑でない技法を用いて明示的に扱えるものとして、計算可能数を選んだ。計算可能数、関数などの相互の関係について、近いうちに説明を与えたいと考えている。これには、計算可能数を用いて表現された実変数の関数の理論の展開も含まれる。私の定義によれば、ある数は、その十進表示を機械によって書き下すことができる場合に計算可能である。

§§ 9, 10では、計算可能数が、自然に計算可能とみなされ得るすべての数を含むことを示すことを意図したいくつかの議論を与える。特に、ある大きなクラスの数が計算可能であることを示す。それらには、例えば、すべての代数的数の実部、ベッセル関数の零点の実部、数$\pi, e$などが含まれる。

1 Computing machines

This section is missing here.

2 Definitions

This section is missing here.

3 Examples of computing machines

This section is missing here.