計算可能数について――決定問題への応用
A. M. Turing 著。
[Received 28 May, 1936.—Read 12 November, 1936.]
「計算可能な」数とは、十進数としての表現が有限の手段によって計算可能である実数、と簡潔に記述することができる。本論文の主題は表向きには計算可能数であるが、整数変数、実変数または計算可能変数の計算可能な関数、計算可能な述語などを定義し研究することも、ほぼ同じ程度に容易である。しかし、そこに含まれる基本的な問題は、いずれの場合にも同じであり、最も煩雑でない技法を用いて明示的に扱えるものとして、計算可能数を選んだ。計算可能数、関数などの相互の関係について、近いうちに説明を与えたいと考えている。これには、計算可能数を用いて表現された実変数の関数の理論の展開も含まれる。私の定義によれば、ある数は、その十進表示を機械によって書き下すことができる場合に計算可能である。
§§ 9, 10では、計算可能数が、自然に計算可能とみなされ得るすべての数を含むことを示すことを意図したいくつかの議論を与える。特に、ある大きなクラスの数が計算可能であることを示す。それらには、例えば、すべての代数的数の実部、ベッセル関数の零点の実部、数などが含まれる。