"ON COMPUTABLE NUMBERS WITH AN APPLICATION TO THE ENTSCHEIDUNGSPROPBLEM"という、アラン・チューリング(1912-1954)の論文を読解します。

担当:ミンギス

1.直訳

2.解釈

3. 補足

_________________________________________________________________________________

1.直訳

「計算可能数と、決定問題への応用」

著者:アラン・チューリング 投稿:1936/05/28 掲載:1936/12/12

「計算可能数」は、実数として簡単に記述されるだろう。ここでいう実数は10進数の表記で、限られた意味で計算できる。この論文のテーマが表面上は「計算可能数」であるにも関わらず、積分変数、実数、計算可能な変数、計算可能な述語における計算可能な函数についても、このテーマは、をほとんど同じように、これらを定義し調査することを簡単にする。例として巻き込まれたこれらの主要な問題は、ところがそれぞれ一緒なのである。だからわたしは、やっかいな技術をなるべく使わないはっきりとした論法のために、「計算可能数」を選んだのである。わたしはすこしだけ、計算可能数と計算可能な函数などとその他のものとの関係を報告したい。これは計算可能数で表記される実数変数函数の理論の発展に寄与するであろう。わたしの定義によれば、機械が数を10進数で書くことができれば、その数は計算できるといえる。

9章と10章で、計算可能数はすべての自然に計算できると思われる数を含んでいることを示すいくつかの根拠を与える。とくに、かなり大きな種類の数も計算できることを示す。それらはたとえば、すべての代数の実数部分やベッセル函数の0の実数部分とかπやeなども、実際に含んでいる。ところが、計算可能数はすべての定義可能な数を含んでいるわけではない。定義できる数が計算できない例を後に与える。

計算可能数の種類はとても多く、そして多くの点で実数の種類と似ているにもかかわらず、それにもかかわらず数え上げることができる。8章でわたしは、逆を証明しているようにみえる確かな根拠を検査する。それらの根拠のうちひとつの正しい応用によって、わたしの結論は、表面的にはゴーデルの結論と似たものにたどり着いた。これらの結果には価値ある応用がある。とくに(11章で)、これらの結果はヒルベルト決定問題に解がないことを示す。

最近のアロンゾ・チャーチの論文には「効果的な計算可能性」のアイディアが導入されたが、これはわたしの「計算可能性」に相当する。しかし、とても違って定義されている。チャーチはまた、決定問題についてわたしに似た結論に到達する。「計算可能性」が「効果的な計算可能性」に相当することの証明は、この論文の付録であらましを述べてある。

つづき→チューリング論文読解1.2

参考https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdfhttp://kitchom.ed.oita-u.ac.jp/jyo/proh09/mkiribu/ronbun.html