Loading article…
チューリングの証明は、アラン・チューリングが1936年11月12日に提出し、1937年に「計算可能な数について、決定問題への応用」というタイトルで初めて出版された証明である[ 1 ] 。これは、ヒルベルトの決定問題の否定、つまり、純粋に数学的なイエス・ノーの質問の中には計算によって答えられないものがあるという予想、より専門的に言えば、決定問題の中には、問題の各インスタンスに対して必ず正しい「イエス」または「ノー」の答えを与える単一のアルゴリズムが存在しないという意味で「決定不能」なものがあるという予想の、チャーチの定理に次ぐ2番目の証明である。チューリング自身の言葉を借りれば、「私が証明しようとしていることは、ゲーデルのよく知られた結果とは全く異なる…私は今、与えられた式UがK [プリンキピア・マテマティカ]で証明可能かどうかを判定する一般的な方法は存在しないことを示す」[ 2 ] 。
チューリングはこの証明に続いてさらに2つの証明を発表した。2番目と3番目の証明はどちらも最初の証明に基づいている。これらはすべて、単純な一連の規則に従うタイプライターのような「計算機」の開発と、その後の「汎用計算機」の開発に基づいている。
チューリングは、決定問題には解が存在しないことを証明する際に、最終的な証明につながる2つの証明から出発した。彼の最初の定理は停止問題に最も関連があり、2番目の定理はライスの定理により関連がある。
第一の証明：任意の「計算機」（整数 1、2、3、…で表される）が「円フリー」（つまり、その数をバイナリで永遠に出力し続ける）であるかどうかを判断できる「計算機」は存在しないこと：「…有限ステップでこれを行う一般的なプロセスはありません」（同書 132ページ）。チューリングの証明は、「対角プロセス」を使用しているように見えますが、実際には、彼のマシン（H と呼ばれる）は、対角数全体（カントールの対角論法）は言うまでもなく、自身の数を計算できないことを示しています：「この論法の誤謬は、B [対角数] が計算可能であるという仮定にあります」[ 3 ]この証明には多くの数学は必要ありません。
2つ目の証明：これはおそらく読者にとってライスの定理としてより馴染み深いものだろう。「任意の機械MのSD［「プログラム」］を与えられたときに、Mが特定の記号（例えば0）を出力するかどうかを判定する機械Eは存在しないことをさらに示すことができる」[ a ]
第三の証明：「各計算機Mに対応して、式Un(M)を構成し、Un(M)が証明可能かどうかを判定する一般的な方法が存在するならば、Mが0を出力することがあるかどうかを判定する一般的な方法が存在することを示す。」[ 2 ]
3つ目の証明では、まず形式論理を用いて最初の補題を証明し、続いて2つ目の補題を簡潔な言葉で証明する必要がある。
最後に、チューリングはわずか64語と記号で背理法を用いて「ヒルベルト決定問題には解が存在しない」ことを証明した。[ 2 ]
チューリングは数多くの略語を生み出した。定義については、記事末尾の用語集を参照のこと。
重要な点をいくつか明確にしておきます。
チューリングマシンHは、対角線上に0と1が並んだ数を表示しようとしています。 この対角線上の数は、Hが評価対象の「成功した」マシンを実際に「シミュレート」し、R番目の「成功した」マシンのR番目の「数値」（1または0）を表示することによって生成されます。
チューリングは論文の大部分を、実際に機械を「構築」することに費やし、その正当性を私たちに納得させようとした。これは、彼が背理法を用いた証明形式に必然的に伴うものであった。この証明の「構築的」な性質を強調する必要がある。チューリングは、実際に構築可能な、現実の機械となり得るものを記述している。唯一疑問視される要素は機械Dの存在であり、この証明によって最終的にそれが不可能であることが示される。
チューリングは、「決定/判定」マシン D の存在を主張することから証明を始める。任意の SD (記号列 A、C、D、L、R、N、セミコロン “;”) を入力すると、この SD (記号列) が「循環的」で「不満足な u」である「循環のない」マシン、つまり「満足できる s」である「計算マシン」を表しているかどうかを判定する。
チューリングは以前、解説の中で、すべての「計算機」（数値を永遠に 1 と 0 で計算する機械）は、「万能機械」U のテープに SD として書き込むことができることを実証しました。最初の証明に至るまでの彼の作業のほとんどは、万能機械が実際に存在することを示すことに費やされました。つまり、 万能機械 U が実際に存在するということです。各数値 N に対して、一意の SD が実際に存在します。すべてのチューリング マシンは SD を持ちます。U のテープ上のすべての SD は U によって「実行」でき、元のマシンと同じ「出力」（図 1、0）を生成します。
チューリングは、機械Dがどのように動作するかについては何も述べていない。議論のために、Dはまず、記号列が「整形式」（つまり、単なる記号の羅列ではなく、アルゴリズムの形式になっているか）であるかどうかを確認し、そうでなければ破棄すると仮定する。次に、「円探し」を行う。このために、おそらく「ヒューリスティック」（教えられた、あるいは学習された手法）を用いるだろう。証明の目的においては、これらの詳細は重要ではない。
チューリングは次に、彼がHと呼ぶ機械が従うべきアルゴリズム（方法）を（やや大まかに）記述する。機械Hは決定機械Dを内包している（したがってDはHの「サブルーチン」である）。機械Hのアルゴリズムは、Hの命令表、あるいはテープに記録されたHの標準記述に表現され、汎用機械Uと統合されているのかもしれないが、チューリングはこの点を明記していない。
チューリングは、万能機械Uを説明する過程で、機械のSD（「プログラム」に似た文字列）を整数（8進数）に変換でき、またその逆も可能であることを実証しました。任意の数N（8進数）は、1をA、2をC、3をD、4をL、5をR、6をN、7をセミコロン「;」に置き換えることでSDに変換できます。
調べてみると、機械Hの固有番号（DN）は「K」という数字である。Kは非常に長い数字、おそらく数万桁にも及ぶ数字であると推測できる。しかし、これは以降の説明には関係ない。
マシン H は、任意の数値 N をサブマシン D がテストするための等価な SD シンボル文字列に変換する役割を担います。（プログラミング用語で言えば、H は任意の「SD」を D に渡し、D は「満足」または「不満足」を返します。）マシン H はまた、成功した数値の集計 R（「記録」？）を保持する役割も担います（「成功」した SD の数、つまり R は、テストされた SD の数、つまり N よりはるかに少ないと想定します）。最後に、H はテープの一部に「ベータプライム」付きの対角線上の数値 B' を出力します。H はこの B' を、（コンピュータの意味で）「満足」した各マシン/数値の「動作」をシミュレートすることによって作成します。最終的に、テスト対象のマシン/数値は R 番目の「数値」（1 または 0）に到達し、H はそれを出力します。 H は、シミュレーションによって残された「後始末」を行い、N を増やしてテストを無限に続ける責任を負います。
注：Hが探しているこれらの機械はすべて、チューリングが「計算機」と呼んだものです。これらは、チューリングが「数字」と呼んだ、1と0の記号のみからなる無限の流れで、2進数と10進数を計算します。
例：機械Hが13472個の数値をテストし、5個の満足のいく数値を生成したとします。つまり、Hは1から13472までの数値をSD（シンボル列）に変換し、テストのためにDに渡しました。その結果、Hは5個の満足のいく数値を集計し、最初の数値を1桁目、2番目の数値を2桁目、3番目の数値を3桁目、4番目の数値を4桁目、5番目の数値を5桁目に処理しました。現在のカウントはN = 13472、R = 5、B' = ".10011"（例）です。Hはテープ上の不要なデータを消去し、次の処理に進みます。
HはN = 13473をインクリメントし、「13473」をシンボル ストリング ADRLD に変換します。サブマシン D が ADLRD を不適切と判断した場合、H はタリー レコード R を 5 のままにします。H は数値 N を 13474 にインクリメントして、処理を続行します。一方、D が ADRLD を適切と判断した場合、H は R を 6 にインクリメントします。H は N を (再度) ADLRD に変換し [これは単なる例であり、ADLRD はおそらく役に立たない]、テスト対象のマシン (U が ADRLD を「実行」している) が 6 番目の「数値」、つまり 1 または 0 を出力するまで、汎用マシン U を使用して「実行」します。H はこの 6 番目の数値 (たとえば「0」) をテープの「出力」領域 (たとえば B' = “.100110”) に出力します。
Hは散らかったものを片付け、それからNの値を13474に増やす。
H が自身の番号 K に到達したときに、プロセス全体が崩壊します。例を進めましょう。成功した集計/記録 R が 12 であるとします。H は最終的に自身の番号から 1 を引いた値、つまり N = K-1 = 4335...321 4に到達しますが、この番号は不成功です。次に、H は N をインクリメントして K = 4335...321 5、つまり自身の番号を生成します。H はこれを「LDDR...DCAR」に変換し、決定マシン D に渡します。決定マシン D は「満足」を返さなければなりません (つまり、H は定義上、無限にテストを続けなければなりません。なぜなら、H は「円なし」だからです)。そこで、H は集計 R を 12 から 13 にインクリメントし、テスト中の番号 K を SD に再変換して、U を使用してそれをシミュレートします。しかし、これは H が自身の動作をシミュレートすることを意味します。シミュレーションが最初に行うことは何でしょうか?このシミュレーション K-aka-H は、新しい N を作成するか、「古い」 N を 1 に「リセット」します。この「K-aka-H」は、新しい R を作成するか、「古い」 R を 0 に「リセット」します。Old-H は、12 番目の数字に到達するまで新しい「K-aka-H」を実行します。
しかし、13桁目には決して到達しません。K-aka-Hは最終的に4335...321 5に到達し、再びテストを繰り返さなければなりません。K -aka - Hは決して13桁目に到達しません。Hマシンはおそらく、空白のテープ上に無限に自身のコピーを印刷しているだけでしょう。しかし、これはHが対角線の数字の1と0を永遠に印刷し続ける満足のいく非循環型計算機であるという前提と矛盾します。（Nを1に、Rを0にリセットした場合も同じことが起こります。）
読者がこれを信じられない場合は、決定機械Dの「スタブ」（スタブ「D」は「満足」を返す）を作成し、機械Hが自身の数値に遭遇した瞬間に何が起こるかを自分で確認すればよい。
1ページにも満たない短い文章で、前提から結論への展開は不明瞭だ。
チューリングは背理法を用いて論証を進めた。彼は、任意の機械MのSD（標準記述、すなわち「プログラム」）を与えられたとき、Mが特定の記号（例えば0）を出力するかどうかを判定する機械Eの存在を主張した。彼は、このMが「計算機」であるとは主張していない。
機械Eが存在することを前提として、チューリングは次のように進める。
証明の難しさは第1段階にある。チューリングが自身の巧妙な手法を説明していないことに気づけば、読者は理解を深めることができるだろう。（要するに、彼は「存在演算子」と「全称演算子」の間の特定の等価性、および論理演算子で記述されたそれらの等価な表現を利用しているのだ。）
例として、数百台の車が停まっている駐車場があるとしましょう。私たちは駐車場全体を回って「パンクした（不良の）タイヤの車」を探すことにしました。1時間ほどで「不良のタイヤの車」を2台見つけました。これで「何台かの車は不良のタイヤを履いている」と断言できます。あるいは、「『すべての車が良質のタイヤを履いている』というのは真実ではない」と言うこともできます。あるいは、「『すべての車が良質のタイヤを履いているわけではない』というのは真実である」と言うこともできます。別の駐車場に行ってみましょう。そこでは「すべての車が良質のタイヤを履いている」ことが分かりました。「不良のタイヤを履いている車は1台もない」と言うこともできます。このように、個々の車について何か言えることがあれば、すべての車についてまとめて何か言えることが分かるのです。
チューリングは次のようにします。M からマシンの集合 { M 1, M 2, M 3, M 4, ..., Mn } を作成し、それぞれのマシンについて「X は少なくとも 1 つの 0 を出力する」という文を書き、真偽値は「真」（空白）または「偽」（:0:）の 2 つだけを許容します。チューリングは、各マシンについて文の真偽値を 1 つずつ決定し、空白または :0:、あるいはそれらの組み合わせの文字列を作成します。たとえば、次のような文字列が得られるかもしれません。「M 1 は 0 を出力する」= 真 AND 「M 2 は 0 を出力する」= 真 AND 「M 3 は 0 を出力する」= 真 AND 「M 4 は 0 を出力する」= 偽、... AND 「Mn は0 を出力する」= 偽。チューリングは文字列を取得します。
BBB:0::0::0: ... :0: ... 無限
機械の数Mnが無限である場合。一方、すべての機械が「True」を生成した場合、テープ上の式は次のようになります。
BBBBB....BBBB ... 無限に
このようにチューリングは、個別に検討された各マシンに関する記述を、それらすべてに関する単一の「記述」（文字列）に変換しました。この式を作成したマシン（チューリングはこれをGと呼んでいます）が与えられれば、彼は自身のマシンEでそれをテストし、0が出力されるかどうかを判断できます。上記の最初の例では、実際に出力されることがわかります。したがって、シーケンス内のすべてのMが0を出力するわけではないことがわかります。しかし、2番目の例では、文字列が空白であるため、シーケンス内のすべてのMnが0を出力したことがわかります。
チューリングに残された課題は、単一のMからMnのシーケンスを生成するプロセスを作り出すことだけだ。
Mが次のようなパターンを出力すると仮定します。
チューリングは、M を受け取り、最初の n 個の 0 を順次「0 バー」( 0 )に変換する Mn のシーケンスを出力する別のマシン F を作成します。
彼は詳細を明かさずに、この機械Fは実際に構築可能であると述べている。いくつかの可能性が考えられる。Fは0を持つ機械を使い果たしてしまうか、あるいは「ゼロをキャンセルする」ための機械を無限に作り続けなければならないかもしれない。
チューリングはここでマシン E と F を組み合わせて複合マシン G を作成します。G は元の M から始まり、F を使用して後継マシン M1、M2、...、Mn をすべて作成します。次に、G は E を使用して、M から始まる各マシンをテストします。E がマシンがゼロを出力しないことを検出した場合、G はそのマシンに対して :0: を出力します。E がマシンが 0 を出力することを検出した場合 (チューリングは述べていませんが、仮定します)、G は :: を出力するか、このエントリをスキップしてマス目を空白のままにします。いくつかのことが起こり得ることがわかります。
すべての Mn が 0 を出力する場合、G は 0 を一切出力しません。または、 すべての M が 0 を出力しない場合、G は無限に 0 を出力します。または、 G はしばらくの間 0 を出力してから停止します。
では、G自体にEを適用するとどうなるでしょうか？
E(G)がGが0を出力しないと判断した場合、すべてのMnが0を出力したことがわかります。そして、すべてのMnがMから来たため、M自体が無限に0を出力していることを意味します。または、 E(G)がGが0を出力すると判断した場合、すべてのMnが0を出力するわけではないことがわかります。したがって、Mは無限に 0を出力しません。
Mが無限に1を出力するかどうかを判断するのと同じプロセスを適用できます。これらのプロセスを組み合わせると、Mが無限に1と0を出力し続けるかどうかを判断できます。したがって、Mが円を含まないかどうかを判断する方法が得られます。証明1により、これは不可能です。したがって、Eが存在するという最初の主張は誤りです。Eは存在しません。
ここでチューリングは「ヒルベルト決定問題には解がない」ことを証明した。[ 2 ]ここで彼は
…関数計算Kの与えられた式Uが証明可能かどうかを判断するための一般的な手順は存在しないことを示している。（同上）
証明に必要な「もし～ならば、そして～に限る」（つまり論理的同値性）を形成するには、補題1と補題2の両方が必要です。
集合Eが計算可能決定可能であるのは、Eとその補集合の両方が計算可能列挙可能である場合に限る（Franzén、p.67）。
チューリングは、実質的に「M のある完全な構成において、テープ上に0が現れる」ことを示す式Un (M)の存在を実証した( 146 ページ)。この式は真であり、つまり「構成可能」であり、彼はその方法を示した。
そしてチューリングは2つの補題を証明する。最初の補題は、すべての苦労を伴う。（2つ目は最初の補題の逆である。）そして彼は背理法を用いて最終結果を証明する。
[読者が証明を詳細に研究しようとする場合は、チューリングが提供した訂正箇所を、第3証明のページのコピーに書き加えて修正する必要があります。また、読者は（i）論理学、（ii）クルト・ゲーデルの論文「プリンキピア・マテマティカの形式的に決定不可能な命題と関連体系について」に関する確かな基礎知識を身につけておく必要があります。[ b ]ゲーデルの論文については、例えばアーネスト・ネーゲルとジェームズ・R・ニューマン著『ゲーデルの証明』（ニューヨーク大学出版局、1958年）を参照してください。]
技術的な詳細を理解するには、読者は「証明可能」の定義を理解し、重要な「手がかり」に気づく必要がある。
ゲーデルの意味で「証明可能」とは、(i) 公理系自体が「この文は証明可能である」という文を生成（表現）するのに十分な力を持っていること、そして (ii) 任意の「整形式」の証明において、記号が公理、定義、および代入によって結論の記号に導かれることを意味する。
最初のヒント：「Mの説明を§6の最初の標準形式に当てはめてみよう」。第6節では、マシンMを「万能マシン」Uのテープ上に「符号化」する非常に具体的な方法について説明しています。そのため、読者はチューリングの万能マシンUと符号化方式のいくつかの特異性を理解しておく必要があります。
（i）汎用マシンは、「命令テーブル」に格納された「汎用」命令のセットです。これとは別に、Uのテープ上には「Mコード」として「計算機」Mが格納されます。汎用命令テーブルは、テープ上に記号A、C、D、0、1、u、v、w、x、y、z、:を 印刷できます。各種マシンMは、Uに印刷を指示することによってのみ、これらの記号を間接的に印刷できます。
(ii) M の「機械語」は、 D、C、A、R、L、N、; という数文字とセミコロンのみで構成されています。M の「コード」には、数値の「数字」（記号）1と0 は一切出現しません。M が U に空白、0、1 の記号を出力させたい場合は、以下のいずれかのコードを使用して U に出力するように指示します。さらにややこしいことに、チューリングはこれらの記号を S0、S1、S2 と呼んでいます。
（iii）「計算機」は、テーブルに直接組み込まれている場合（最初の例が示すように）、または汎用マシンUのテープ上のマシンコードMとして、空白テープ（Mコードがある場合はその右側）に1と0として番号を永久に右方向に印刷します。
（iv）「計算機」が U+「M コード」である場合、テープにはまず「M コード」が現れます。テープには左端があり、「M コード」はそこから始まり、交互に右方向に進みます。M コードが終了すると（これらの M コードが有限アルゴリズムであるという仮定のため、必ず終了します）、数字は交互に1と0で始まり、右方向に永遠に続きます。チューリングは、（空白の）交互に現れるマス目（「E」-「消去可能」マス目と呼ばれる）を使用して、U+「M コード」が M コード内と、マシンが出力する「数字」の両方で計算が行われている場所を追跡できるようにします。
（v）「完全な構成」とは、テープ上のすべてのシンボル（Mコードとそれまでの「図形」を含む）と、現在スキャン中の図形（スキャン中のシンボルの左側にポインタ文字を印刷したもの？）を印刷することである。チューリングの意図を正しく解釈していれば、これは非常に長いシンボルの集合となる。しかし、Mコード全体を繰り返す必要があるかどうかは不明である。現在のMコード命令の印刷と、図形マーカー付きのすべての図形の印刷のみが必要である。
(vi) チューリングは、「Mコード」（テープに表示されるMのコード）に含まれる膨大な数の命令を、次のような3つの標準的なセットに縮小しました。{qi Sj Sk R ql} 例えば、マシンが命令#qiを実行中で、シンボルSjがスキャン中のマスにある場合、シンボルSkを印刷して右に進み、次に命令qlに進みます。他の命令も同様で、「左」Lと「移動なし」Nをエンコードします。このセットは、シンボルの文字列qi = DA...A、Sj = DC...C、Sk = DC...C、R、ql = DA....Aによってエンコードされます。各命令はセミコロンで区切られます。例えば、{q5, S1 S0 L q3}は、命令#5: スキャンされたシンボルが0の場合、空白を印刷し、左に進み、次に命令#3に進むことを意味します。これは次のようにエンコードされます。
; DAAAAADCDLDAAA
2つ目の手がかり：チューリングはゲーデルの論文で導入されたアイデア、つまりUn (M) の公式の（少なくとも一部）の「ゲーデル化」を利用している。この手がかりは、138 ページ（ Davis (1965) 、p. 138 ）の脚注としてのみ現れる。「r 個の素数の列は^ (r) で表される」（同上）[ここで、括弧内の r は「上げられている」。] この「素数の列」は F^(n) と呼ばれる公式に現れる。
3つ目の手がかり：これは2つ目の手がかりを補強する。チューリングが最初に証明を試みた際に使用した表現は次の通りである。
(Eu)N(u) & (x)(... etc. ...) [ 6 ]
論文の前半でチューリングは既にこの表現（ 138ページ）を使用し、N(u)を「uは非負整数である」（同上）（つまりゲーデル数）と定義していた。しかし、ベルネイズの修正により、チューリングはこのアプローチ（つまりN(u)の使用）を放棄し、「ゲーデル数」が明示的に現れるのは、F^(n)を使用している箇所のみである。
これは証明にとって何を意味するのでしょうか？最初のヒントは、テープ上のMコードを単純に調べても、U+"Mコード"によってシンボル0が印刷されたことがあるかどうかは分からないということです。テストマシンは、命令を表すシンボル列のいずれかにDCが現れるかどうかを調べるかもしれません。しかし、この命令は実際に「実行される」のでしょうか？それを知るには、何かが「コードを実行する」必要があります。この何かはマシンでも、形式証明の行、つまり補題1でも構いません。
2番目と3番目の手がかりは、その基礎がゲーデルの論文にあるため、証明が難しいことを意味している。
以下の例では、実際に簡単な「定理」を構築します。それは、ポストチューリングマシンの小さなプログラム「実行」です。適切に設計された定理がいかに機械的であるかを見てみましょう。証明とは、まさにその名の通り、定理の「テスト」であり、冒頭に「証明例」を挿入して、最後に何が出てくるかを確認することで行います。
証明に必要な「もし～ならば、そして～に限る」（つまり論理的同値性）を形成するには、補題1と補題2の両方が必要です。
集合Eが計算可能決定可能であるのは、Eとその補集合の両方が計算可能列挙可能である場合に限る。（フランツェン、67ページ）
フランツェンの言葉を引用すると：
文Aが形式体系Sにおいて決定可能であるとは、文Aまたはその否定のいずれかがSにおいて証明可能である場合をいう。（フランツェン、65ページ）
フランツェンは著書の中で既に「証明可能」という言葉を定義している。
形式体系とは、公理（形式的に定義された言語で表現される）と推論規則（推論規則とも呼ばれる）からなる体系であり、これらの規則を用いて体系の定理を導出する。定理とは、公理から出発して推論規則を一連の適用することで得られる、体系の言語におけるあらゆる命題である。証明とは、そのような適用を有限回繰り返すことで、最終的に定理を導き出すものである。（同書、 17ページ）
つまり、「文」とは記号の列であり、定理とは記号の列の列である。
チューリングは次のような課題に直面している。
ユニバーサルチューリングマシンの「プログラム」とテープ上の数値記号（チューリングの「数字」、記号「1」と「0」）を「定理」、つまりマシンの連続動作、テープ上の（すべての）数字、および「テープヘッド」の位置を定義する（途方もなく長い）一連の文に変換する。
したがって、「文の列」は記号の列の列になります。使用できる個々の記号は、ゲーデルの論文で定義された記号のみです。（以下の例では、「図」を「<」と「">」で囲むことで、「図」が機械によってスキャンされる記号であることを示しています。）
以下では、チューリングの「計算機」はすべて、空白のテープ上で動作を開始する二進数生成器／作成器であることを改めて確認する必要があります。適切に構築されていれば、常に無限に動作し続けますが、その命令は常に有限です。チューリングの証明では、チューリングのテープには「左端」がありましたが、右方向には無限に伸びていました。以下の例では、「機械」は万能機械ではなく、表に示された命令を持つより単純な「専用機械」であると仮定します。
この例は、チューリングマシンの修正版ポストチューリングマシンモデルに基づいています。このモデルでは、記号0と1のみを出力します。空白のテープはすべてbであるとみなされます。修正版モデルでは、7つのポストチューリング命令にさらに2つの命令を追加する必要があります。使用する略語は次のとおりです。
R、右: 右を見てテープを左に移動するか、テープヘッドを右に移動 L、左 : 左を見てテープを右に移動するか、テープヘッドを左に移動 E、スキャンした正方形を消去 (例: 正方形を空白にする) P0、: スキャンした正方形に 0 を印刷 P1、: スキャンした正方形に 1 を印刷 Jb_n、空白の場合は命令 #n に ジャンプ、J0_n、0 の場合は命令 #n に ジャンプ、J1_n、1 の場合は命令 #n にジャンプ、 停止。
R、L、E、P0、P1の場合、機械はタスクを完了した後、数値順に次の命令に進みます。ジャンプ命令の場合も同様で、テストが失敗した場合はジャンプ命令が実行されます。
しかし、簡潔にするため、ここでは3つの正方形のみを使用します。そして、これらは常に左側にスキャンされた正方形がある空白から始まります。つまり、bbbです。1、0、空白の2つの記号を使用すると、27種類の異なる構成が可能になります。
bbb、bb0、bb1、b0b、b00、b01、b1b、b10、b11、0bb、0b0、0b1、00b、000、001、01b、010、011、1bb、1b0、1b1、10b、100、101、11b、110、111
ここで注意が必要なのは、アルゴリズムが（一時的に）数字の間に空白を残し、後で何かを埋める可能性があるからです。さらに可能性が高いのは、アルゴリズムが意図的にそうするということです。実際、チューリングマシンはまさにそうしています。交互のマス目に印刷し、数字の間に空白を残すことで、位置記号を印刷できるようにしているのです。
チューリングは常に交互のマス目を空白にして、機械が図形の左側に記号（または、機械が万能機械で、スキャンされたマス目が実際に「プログラム」内にある場合は文字）を配置できるようにしていました。この小さな例では、これを省略して、スキャンされた記号の周りに記号（ ）を配置します。以下はその例です。
b(b)0 これは、「テープは左側の空白の左側に空白があるが、左側の空白は『有効』であり、スキャンされたマスは空白で『0』、右側に空白がある」という 意味です。 1(0)1 これは、「テープは左側に空白があり、次に1、スキャンされたマスは『0』」という意味です。
簡単なプログラムを書いてみましょう。
開始: P1、R、P1、R、P1、H
常に空のテープから始めることを覚えておいてください。完全な構成では、テープにシンボルが印刷され、続いて次の命令が印刷されます。
開始設定: (b) P1、 設定 #1: (1) R、 設定 #2: 1(b) P1、 設定 #3: 1(1) R、 設定 #4: 11(b) P1、 設定 #5: 11(1) H
式に「ジャンプ」を追加してみましょう。そうすると、完全な構成にテープ記号を含める必要がある理由がわかります。（実際には、以下でより分かりやすく説明します。）この小さなプログラムは、右に3つの「1」を出力し、方向を反転して左に移動し、空白に到達するまで0を出力します。マシンが使用するすべての記号を出力します。
開始: P1、R、P1、R、P1、P0、L、J1_7、H (b)bb P1、 (1)bb R、 1(b)b P1、1 (1)b R、 11(b) P1、11 (1) P0、11 (0) L、 1(1)0 J1_7 1(1)0 L (1)10 J0_7 (1)10 L (b)110 J0_7 (b)110 H
最後に、左側の空白が「重要な役割を果たすようになった」ことがわかったので、それを全体の構成の一部として残しておきます。
我々が正しく作業を完了したと仮定して、開始条件を追加し、「定理がどこに当てはまるか」を確認します。結果として得られる構成、つまり数字の110が証明です。
チューリングの証明は多数の定義によって複雑化しており、マーティン・デイビスが「些細な技術的詳細」や「…与えられた技術的詳細が間違っている」と呼んだものと混同されている。[ c ]チューリング自身は1938年に「訂正」を発表し、「著者はこれらの誤りを指摘してくれたP.ベルネイズに感謝している」と述べている。[ 7 ]
具体的には、第3証明は原文のままでは技術的な誤りが多発している。ベルネイズの提案やチューリングの修正後も、万能機械の説明には誤りが残っていた。さらに紛らわしいことに、チューリングは原論文を修正できなかったため、本文中にはチューリングの欠陥のある最初の試みを彷彿とさせる記述が見られる。
ベルネイズによる訂正は、デイビス（1965）の152～154ページに掲載されています。原文は「計算可能な数について、決定問題への応用。訂正」、ロンドン数学会紀要（2）、43（1938）、544～546ページに掲載されています。
チューリングの論文のオンライン版には、これらの訂正が補遺として記載されていますが、万能機械に関する訂正は、エミール・ポストによる分析の中に見つける必要があります。
当初、証明の詳細に細心の注意を払った唯一の数学者はポストであった（ホッジス著、 125ページ参照）。これは主に、彼が同時に「アルゴリズム」を原始的な機械的な動作に還元するという同様の結論に達していたため、証明に個人的な関心を持っていたからである。奇妙なことに（おそらく第二次世界大戦の影響があったのだろう）、ポストがそれを分析するのに約10年かかり、1947年の論文「チューの問題の再帰的不確定性」の付録に掲載した。 [ d ]
他にも問題が浮上する。ポストは付録で、論文の難しさについて間接的に、証明の「概略的な性質」 [ e ]と「直感的な形式」 [ e ]について直接的にコメントしている。ポストは様々な点を推論しなければならなかった。
我々の批判が正しければ、無限個の0と1を出力するチューリング計算機であれば、その機械は円フリーであると言われる。そして、問題となっているチューリングの2つの定理は、実際には次の通りである。任意の正の整数nを与えられたとき、nが円フリーのチューリング計算機のDNであるかどうかを判定するチューリング計算機は存在しない。[第二に]、任意の正の整数nを与えられたとき、nが特定の記号（例えば0）を出力するチューリング計算機のDNであるかどうかを判定するチューリング規約機械は存在しない。[ f ]
1.計算可能な数— 機械（つまり、アルゴリズムなどの有限な手段）によって小数点以下を計算できる数
2 M — 有限命令テーブルとスキャン/印刷ヘッドを備えた機械。M は、それぞれ「記号を保持できる」正方形に分割された無限テープを移動します。機械命令は次のとおりのみです。1 マス左に移動、1 マス右に移動、スキャンされた正方形に記号 p を印刷、スキャンされた正方形を消去、記号が p の場合は命令 aaa を実行、スキャンされた記号が p でない場合は命令 aaa を実行、スキャンされた記号がない場合は命令 aaa を実行、スキャンされた記号が任意の場合は命令 aaa を実行 [ここで「aaa」は命令識別子です]。
3計算機- 2 種類の記号を出力する M 。第 1 種類の記号は「数字」と呼ばれ、バイナリ記号 1 と 0 のみである。第 2 種類の記号は、それ以外の任意の記号である。
4つの数字― 記号1と0、別名「第一種記号」
5 m構成— 命令識別子。命令テーブル内の記号、または汎用マシンのテープ上の命令番号を表す記号列（例：「DAAAAA = #5」）
第2種記号6個 ― 1と0以外の記号
7円形― 計算に失敗した計算機。計算した数値を二進数で表す0または1を無限に出力できない。
8.円なし計算機 ― 成功した計算機。計算した数値を二進数で表した0または1の数字を無限に出力する。
9シーケンス— 「機械によって計算されたシーケンス」のように: 第一種の記号、別名数字、別名記号 0 と 1。
10 計算可能な数列— 円を使わない機械で計算可能
11 SD – 標準記述：チューリングマシンのテープ上の記号A、C、D、L、R、N、「;」のシーケンス
12 DN —説明番号: SD を番号に変換したもの: 1=A、2=C、3=D、4=L、5=R、6=N、7=;
13 M(n) — DNが「n」である機械
14満足— 円のない機械を表す SD または DN
15 U ― 「汎用」命令テーブルを備えたマシン。U に「ある計算機 M の SD が先頭に書き込まれたテープが供給されると、U は M と同じシーケンスを計算する」。
16 β' —「ベータプライム付き」: n 番目の計算可能数列の n 番目の数字 (つまり 0 または 1) で構成される、いわゆる「対角数」[また、H の計算可能数、下記参照]
17 u — 不十分な、つまり円形の SD
18秒— 良好、つまり円のないSD
19 D — Hに含まれる機械（下記参照）。任意の計算機MのSDが与えられると、DはMのSDをテストし、円形であれば「u」、円形でなければ「s」とマークする。
20 H — 計算機。H は B' を計算し、R と N を維持します。H には D と U と、N と R を維持し、D に N の等価 SD を提供する未指定の機械 (またはプロセス) が含まれています。E は B' の数値を計算し、B' の数値を組み立てます。
21 R — Dによってテストされた成功した（円のない）SDの数の記録または集計
22 N — 1 から始まる数値で、機械 E によって SD に変換されます。E は N を保持します。
23 K — 数字。H の DN。
5 m構成— 命令識別子。命令テーブル内の記号、または汎用マシンのテープ上の命令番号を表す記号列（例：「DAAAAA = 命令番号5」）。チューリングのSDでは、m構成は各命令に2回出現し、左端の文字列が「現在の命令」、右端の文字列が次の命令です。
24完全な構成— スキャンされた正方形の番号 (図1または0 )、テープ上のすべてのシンボルの完全なシーケンス、および m 構成 (命令識別子。シンボルまたは番号を表すシンボルの文字列。例: "命令 DAAAA = #5")
25 RSi(x, y) — 「Mの完全配置xにおいて、yの正方形上の記号はSiである。「完全配置」は定義#5である」
26 I(x, y) — 「Mの完全な構成xにおいて、正方形yが走査される」
27 Kqm(x) — 「Mの完全な構成xにおいて、マシン構成（命令番号）はqmである」
28 F(x,y) — 「yはxの直後の後継である」（ゲーデルが後継関数として「f」を用いたことに倣う）。
29 G(x,y) — 「xはyに先行する」が、必ずしも直後とは限らない
30 Inst{qi, Sj Sk L ql}は略語であり、Inst{qi, Sj Sk R ql}およびInst{qi, Sj Sk N ql}も同様です。下記を参照してください。
チューリングは命令セットを3つの「標準形式」に絞り込んだ。左移動、右移動、そして移動なしを表す形式である。SiとSkはテープ上の記号である。
例えば、最初の行の操作は、PSk = PRINT symbol Sk from the collection A, C, D, 0, 1, u, v, w, x, y, z, : , then move tape LEFT です。
これらをさらに次のように略記した：（N1）qi Sj Sk L qm （N2）qi Sj Sk R qm （N3）qi Sj Sk N qm
証明3では、彼はこれらの最初のものを「Inst{qi Sj Sk L ql}」と呼び、機械SD全体を論理積（論理OR）として記述する方法を示しています。この文字列は「Des(M)」と呼ばれ、「Description-of-M」のようになります。つまり、機械が右に交互に0、次に1、0を無限に出力すると、次の表になる可能性があります（同様の例が119ページに掲載されています）。
q1、空白、P0、R、q2 q2、空白、P-空白、R、q3 q3、空白、P1、R、q4 q4、空白、P-空白、R、q1
（これは「p空白」命令で正規形に簡略化されているため、チューリングの例とは少し異なります。）これらを「Inst( )形式」にすると、命令は次のようになります（S0は空白、S1=0、S2=1であることを覚えておいてください）。
Inst {q1 S0 S1 R q2} Inst {q2 S0 S0 R q3} Inst {q3 S0 S2 R q4} Inst {q4 S0 S0 R q1}
標準記述（SD）への縮小は以下のとおりです。
;ダッドクラダア ; DAADDRDAAA ;だああああああああああ ;ダアアドルダ ;
これは、彼の著書にある例と一致します（各文字と数字の間には空白があります）。ユニバーサルマシンUは、交互に配置された空白のマスを「ポインタ」を配置する場所として使用します。
{{cite journal}}: CS1メンテナンス: 日付と年 (リンク)