チューリングマシンの例

以下は、チューリングマシンの記事を補足する例です。

次の表はチューリングの最初の例です (Turing 1937)。

「1. 0 1 0 1 0 1...というシーケンスを計算するマシンを構築できます」（0 <空白> 1 <空白> 0...）^[1]

機械が実際にどのような動作を行うかについて、チューリング（1936）^[2]は次のように述べています。

「この[例]表(および同種の後続の表すべて)は、最初の2列に記述された構成に対して、3列目の操作が連続して実行され、その後、マシンが最後の列のm構成に移行することを意味するものと理解される。」^[2]

彼は、上記の表を「b」という単一の命令に縮小したときに、これを非常に明確にしています。 ^[3]しかし、彼の命令は3行で構成されています。命令「b」には、3つの異なるシンボルの可能性があります{なし、0、1}。各可能性の後に、右端の列に到達するまで一連のアクションが続き、最終的なm構成は「b」になります。

チューリング (1937) 自身を含む多くの評論家 (例: ポスト (1936)、ポスト (1947)、クリーネ (1952)、ワン (1954)) が指摘しているように、チューリング命令はアトミックではありません。つまり、計算能力を低下させることなく、モデルをさらに単純化することができます。詳細については、ポストチューリング マシンを参照してください。

記事「チューリングマシン」で述べられているように、チューリングはテーブルをさらに細分化して、1回の印刷/消去とそれに続く1回のテープ移動L/R/Nのみを許可することを提案しました。彼は変換された最初の小さなテーブルの例を次に示します。^[4]

チューリングの声明は、依然として 5 つのアトミック操作を暗示しています。特定の命令 (m 構成) では、マシンは次の操作を実行します。

1. 頭の下のテープのシンボルを観察する
2. 観察されたシンボルに基づいて、適切な命令シーケンスが使用される
3. シンボルS _jを印刷するか、消去するか、何もしない
4. テープを左、右に動かすか、まったく動かさないか
5. そのシンボルの最終的なm構成に進みます

チューリング マシンの動作はアトミックではないため、マシンのシミュレーションでは、5 つのタプルをそれぞれより単純な一連の動作にアトミック化する必要があります。次のマシンの「動作」の例で使用されている 1 つの可能性は次のとおりです。

(q _i ) ヘッドの下のテストテープシンボル: シンボルがS ₀の場合はq _i .01に進み、シンボルS _{1の場合はq i} .11に進み、シンボルS _{2の場合はq i} .21に進みます。

(q _i .01) シンボルS _j 0を印刷するか、消去するか、何もせずにq _i .02に進む

(q _i .02) テープを左または右に動かすか、まったく動かさない場合はqm0に進みます

(q _i .11) シンボルS _j 1を印刷するか、消去するか、何もせずにq _i .12に進む

(q _i .12) テープを左または右に動かすか、まったく動かさない場合はqm1に進みます

(q _i .21) シンボルS _j 2を印刷するか、消去するか、何もせずにq _i .22に進む

(q _i .22) テープを左または右に動かすか、まったく動かさない場合はqm2に進みます

（など、すべての記号を考慮する必要があります）

いわゆる「標準的な」有限状態マシンは、シンボル テストを「並列に」実行します。詳細については、マイクロプログラミングを参照してください。

マシンが実行する次の例では、チューリングのモデルのいくつかの特殊性に注目します。

数字を交互のマス目にのみ書くという慣習は非常に便利です。私は常にこれを使用します。^[2]

そのため、印刷するときには、1 つおきのマス目を飛ばします。印刷されたマス目は F マス目と呼ばれ、その間の空白のマス目は「マーカー」として使用でき、「消去可能」という意味で「E マス目」と呼ばれます。F マス目は、彼の「数字マス目」であり、1 または 0 の記号のみが表示されます。彼はこの記号を「数字」(「2 進数」のように) と呼んでいました。

この例では、テープは「空白」から始まり、その後「数字」が印刷されます。簡潔にするために、ここでは表の状態のみを示します。

すべての中間テープ印刷と移動を含む同じ「実行」を次に示します。

表をよく見ると、チューリング自身の例にいくつかの問題があることがわかります。すべての記号が考慮されているわけではないのです。

たとえば、テープが最初は空白ではなかったとします。何が起こるでしょうか? チューリング マシンは、意図した値とは異なる値を読み取るでしょう。

これは、「乗算」ルーチンで使用される非常に重要なサブルーチンです。

サンプルのチューリング マシンは、0 と 1 の文字列を処理します。0 は空白記号で表されます。そのタスクは、テープ上で検出された 1 の連続を、その間に 0 を書き込むことによって 2 倍にすることです。たとえば、ヘッドが「111」を読み取ると、0 を書き込み、次に「111」を書き込みます。出力は「1110111」になります。

このチューリング マシンがタスクを実行するには、{s ₁、s ₂、s ₃、s ₄、s ₅ } と呼ばれる 5 つの動作状態のみが必要です。各状態は 4 つのアクションを実行します。

1. 頭の下のシンボルを読んでください
2. 状態によって決まる出力シンボルを書き込む
3. 状態に応じてテープを左または右に動かします
4. 現在の状態によって決定される次の状態に切り替える

印刷操作:シンボルSまたはEを印刷するか、何もしない

マシンの「実行」は、16 個のマシン構成 (チューリング状態とも呼ばれます) を順番に実行します。

_{このマシンの動作はループとして説明できます。 s 1}から始まり、最初の 1 を 0 に置き換え、次に s _{2 を}使用して右に移動し、1 と最初に見つかった 0 をスキップします。次に s _{3 は}、次の 1 のシーケンス (最初は 1 はありません) をスキップし、最初に見つかった 0 を 1 に置き換えます。 s _{4 は}左に戻り、0 が見つかるまで 1 をスキップして s ₅に切り替えます。次に s _{5 は左に移動し、 s 1}によって最初に書き込まれた 0 が見つかるまで 1 をスキップします。

0 を 1 に置き換え、1 つ右に移動して、ループの次のラウンドで 再び s _{1に入ります。}

_{これは、s 1 が}0 (2 つの 1 の文字列の中央にある 0) を見つける まで続き、その時点でマシンは停止します。

別の説明では、問題は「1」がいくつあるかをどのように追跡するかであると考えられています。可能な数ごとに 1 つの状態 (0、1、2、3、4、5、6 などのそれぞれに状態) を使用することはできません。そうすると、すべての自然数を表すために無限の状態が必要になり、状態マシンは有限であるため、何らかの方法でテープを使用してこれを追跡する必要があります。

基本的な仕組みは、前後に移動して各「1」を反対側にコピーすることです。移動のどの部分にあるかを覚えておくほどインテリジェントです。さらに詳しく説明すると、中央の分離「0」を認識し、反対側の「0」を認識して終了点に到達したことを認識し、各「1」を反対側に運びます。同じ方法で戻ってきて、中央の「0」を検出し、次に元の側の「0」を検出します。元の側のこの「0」が、1 の数をどのように追跡するかというパズルの鍵となります。

トリックは、「1」を繰り上げる前に、その数字を「0」に置き換えて「使用済み」としてマークすることです。戻るときに、その「0」を「1」で埋め戻し、次の数字に移動して「0」でマークし、サイクルを繰り返し、その「1」を繰り上げます。 往復するたびに、マーカー「0」は中心に一歩近づきます。このようにして、どれだけの「1」を横切ったかを記録します。

戻ると、マーカー「0」は「1」の集合の終わりのように見えます。すでに渡された「1」はマーカー「0」の反対側には見えず、そのため、数学的帰納法による証明と同様に、(N-1) 個の「1」を操作しているかのように見えます。

中間の「動作」の結果を示す完全な「実行」。

次のチューリング命令表はピーターソンから派生したものです。^[5]ピーターソンはヘッドを動かします。次のモデルではテープが動きます。

3 状態のビジービーバーの「状態」の図は、実際に「状態」を実行するために必要なイベントの内部シーケンスを示しています。前述のように、チューリング (1937) は、これが命令を記述する 5 組の適切な解釈であることを完全に明らかにしています。^[1]チューリングの 5 組の原子化の詳細については、ポストチューリングマシンを参照してください。

次の表は、チューリング状態のみの「圧縮された」実行を示しています。

3 状態のビジー ビーバーの完全な「実行」。結果として生じるチューリング状態 (チューリングが「m 構成」、つまり「マシン構成」と呼んだもの) は、列 A に灰色で強調表示され、マシンの命令の下にも表示されます (列 AF-AU)。

• ピーターソン、アイヴァース（1988年）。『数学の旅人：現代数学のスナップショット』ニューヨーク：WHフリーマン・アンド・カンパニー。ISBN 0-7167-2064-7。
• デイビス、マーティン(1965)。『決定不能なもの：決定不能な命題、解決不能な問題、計算可能な関数に関する基本論文』ニューヨーク：レイヴン・プレス。
• チューリング、アラン（1937）。計算可能数について、そしてその計算問題への応用。p.116。
• チューリング、アラン（1937）。計算可能数について、そしてその計算問題への応用。訂正。p.152-154。