私は、1936 年のアラン・チューリングの論文「解像度の問題への応用による計算可能な数について」の最初のページの翻訳を紹介します。最初の章には、後に現代のコンピューティングの基礎となるコンピューターの説明が含まれています。
この記事の完全な翻訳と説明は、アメリカの普及者 Charles Petzold による書籍「Reading Turing: A Journey through Turing’s Historical Article on Computability and Turing Machines」(ISBN 978-5-97060-231-7、978-0-470-22905-7) で読むことができます。
元の記事:
https://www.astro.puc.cl/~rparra/tools/PAPERS/turing_1936.pdf
解像度問題への応用による計算可能な数値について
午前チューリング
[1936 年 5 月 28 日に受領 – 1936 年 11 月 12 日に読了]
「計算可能な」数値は、小数としての表現が有限の方法で計算できる実数として簡単に説明できます。一見すると、この記事では数値を計算可能なものとして扱いますが、整変数、実数変数、計算可能な変数、計算可能な述語などの計算可能な関数を定義して調査することは、ほぼ同じくらい簡単です。ただし、これらの計算可能なオブジェクトに関連する基本的な問題は、どの場合でも同じです。詳細な検討のために、計算可能な数値を考慮する方法が最も面倒ではないため、計算可能なオブジェクトとして計算可能な数値を選択しました。計算可能な数値と計算可能な関数などの関係については、近いうちに説明したいと思っています。同時に、計算可能な数値で表現される実変数の関数理論の分野でも研究が行われます。私の定義によれば、実数は、その 10 進数表現が機械で記述できる場合に計算可能です。
パラグラフ 9 と 10 では、計算可能な数値には、当然計算可能であると考えられるすべての数値が含まれることを示すために、いくつかの議論を示します。特に、いくつかの大きなクラスの数値が計算可能であることを示します。これらには、たとえば、すべての代数的数値の実部、ベッセル関数のゼロの実部、数値 π、e などが含まれます。ただし、次の計算不可能な定義可能な数値の例でわかるように、計算可能な数値には定義可能な数値がすべて含まれるわけではありません。
計算可能な数値のクラスは非常に大きく、多くの点で実数のクラスと似ていますが、依然として数えることが可能です。 §8 では、反対と思われる特定の議論を検討します。これらの議論の 1 つが正しく適用されると、一見するとゲーデル* の結論と似た結論が導き出されます。これらの結果は非常に重要な応用分野を持っています。特に、以下に示すように (§11)、解像度の問題には解決策がありません。
最近の記事で、アロンゾ・チャーチは「実効計算可能性」という考え方を紹介しました。これは私の「計算可能性」という考え方と同じですが、定義はまったく異なります。チャーチも解決の問題に関して同様の結論に達しています。 「計算可能性」と「効率的に計算可能」が同等であることの証明は、この記事の付録に示されています。
1. コンピュータ
計算可能な数とは、小数点以下の桁が有限の方法で数えられる数であることはすでに述べました。ここではより明確な定義が必要です。この記事では、§9 に到達するまで、ここで与えられた定義を正当化する実際の試みは行いません。今のところ、（このための）（論理的な）根拠は、人間の記憶には必然的に限界があるということだけを述べておきます。
実数を計算する過程にある人間と、有限数の条件 q1、q2、…、qR のみを満たすことができる機械を比較してみましょう。これらの条件を「m 構成」と呼びます。この（つまり、そのように定義された）マシンには「テープ」（紙に似たもの）が装備されています。機械内を通過するこのベルトはいくつかのセクションに分かれています。それらを「正方形」と呼びましょう。このような各正方形には、何らかの「シンボル」を含めることができます。いつでも、「このマシン内にある」シンボルを含むそのような正方形は 1 つだけ、たとえば r 番目の正方形だけです。このような正方形を「スキャンされたシンボル」と呼びます。 「スキャンされた文字」は、いわばマシンが「直接認識している」唯一の文字です。ただし、m 構成を変更することで、マシンは以前に「見た」(スキャンした) 文字の一部を効果的に記憶できるようになります。いつでもマシンの可能な動作は、m 構成 qn とスキャンされたシンボル *** によって決まります。このシンボルのペアを qn、「構成」と呼びましょう。このように指定された構成によって、特定のマシンの可能な動作が決まります。スキャンされた正方形が空白である (つまり、文字が含まれていない) 構成の一部では、マシンはスキャンされた正方形に新しい文字を書き込み、その他の構成ではスキャンされた文字を消去します。このマシンは移動して別のマスをスキャンすることもできますが、この方法では右または左に隣接するマスにのみ移動できます。これらの操作に加えて、マシンの m 構成を変更することもできます。この場合、書かれた文字の一部は、計算される実数の小数部分である一連の数字を形成します。残りは「記憶を助ける」ための不正確なマークにすぎません。この場合、上記の不正確なマークのみを消去することができる。
ここで考慮される演算には、計算で使用されるすべての演算が含まれると主張します。このステートメントの理論的根拠は、機械理論を理解している読者にとっては理解しやすいものです。したがって、次のセクションでは、「マシン」、「テープ」、「スキャンされた」などの用語の意味の理解に基づいて、問題の理論を展開していきます。
*ゲーデル「プリンキピア数学 (1910 年、1912 年、1913 年にホワイトヘッドとラッセルによって出版) および関連システムの形式的に決定不可能な文について、第 1 部」数学ジャーナル。 『物理学』ドイツ語月刊誌第 38 号 (1931 年、173-198 ページ)。
** アロンゾ・チャーチ、「初等整数理論における決定不可能な問題」、American J. of Math.、第 58 号 (1936 年)、345-363 ページ。
*** アロンゾ チャーチ、「解決の問題に関するメモ」、J. of Symbolic Logic、No. 1 (1936)、40-41 ページ
Leave a Reply