チューリングマシンの停止性入門：停止するマシン・停止しないマシンのシミュレーター解説
はじめに：チューリングマシンにおける「停止」の重要性
チューリングマシンは、計算のモデルとして非常に強力であり、現代のコンピュータの基礎となる理論です。チューリングマシンが行う「計算」は、入力されたテープ上の記号を読み取り、内部の状態と遷移規則に従ってテープに書き込み、ヘッドを移動させる一連の操作です。この操作がいつか終了し、結果が得られることを「計算が停止する」と呼びます。
計算が停止することは、その計算が有限の時間内に完了し、何らかの出力を得られることを意味します。しかし、チューリングマシンの中には、入力によってはいつまでも計算を終えずに動き続けるものも存在します。このような計算は「停止しない」計算と呼ばれます。
本記事では、チューリングマシンにおける停止性の概念を掘り下げ、具体的に「停止するチューリングマシン」と「停止しないチューリングマシン」の例を挙げ、シミュレーターでその動作を追うことで、この重要な概念への理解を深めていきます。
チューリングマシンの停止とは？
チューリングマシンは、以下のような要素で定義されます。 * 状態の有限集合 $Q$ * テープアルファベット $\Sigma$ * 空白記号 $B \in \Sigma$ * 入力アルファベット $\Gamma \subseteq \Sigma \setminus {B}$ * 開始状態 $q_0 \in Q$ * 受理状態の集合 $F \subseteq Q$ * 遷移関数 $\delta: Q \times \Sigma \to Q \times \Sigma \times {L, R, S}$ (L: 左移動, R: 右移動, S: 移動なし)
チューリングマシンが計算を終了し、停止する方法は主に二つあります。
- 受理状態への遷移: マシンがある受理状態 $q_f \in F$ に遷移した場合、そこで計算は停止し、入力は「受理された」と見なされます。
- 遷移規則の不在: 現在の状態 $q$ とヘッドが読み取った記号 $\sigma$ に対して、遷移関数 $\delta(q, \sigma)$ が定義されていない場合、マシンはそこで停止します。この場合、入力が受理されたかどうかは、停止した時の状態が受理状態であったかどうかによります（通常、受理状態以外での遷移不在による停止は受理とは見なされません）。サイトのシミュレーターでは、受理状態への遷移を主な停止条件としている場合が多いですが、遷移不在による停止も実装によってはサポートされます。
計算が停止しない場合は、ヘッドが無限に移動し続けるか、あるいは同じ状態とテープの内容の組み合わせを無限に繰り返す（無限ループ）かのいずれかとなります。
停止するチューリングマシンの例：入力全体をスキャンする
簡単な停止するチューリングマシンの例として、「入力テープ上の記号をすべて読み取り、右端に到達したら停止する」というマシンを考えてみましょう。入力としては、例えば 0101 のような有限の文字列が与えられ、その右側は空白記号 B で埋められているとします。
このマシンは、開始状態 $q_0$ から右方向へヘッドを移動し続け、空白記号 B を読み取ったら停止状態 $q_f$ に遷移します。
マシンの仕様例:
- 状態 $Q = {q_0, q_1, q_f}$
- テープアルファベット $\Sigma = {0, 1, B}$
- 開始状態 $q_0$
- 受理状態 $F = {q_f}$
- 遷移関数 $\delta$:
- $\delta(q_0, 0) = (q_0, 0, R)$ (0を読んだら0を書き、右へ移動、状態は$q_0$のまま)
- $\delta(q_0, 1) = (q_0, 1, R)$ (1を読んだら1を書き、右へ移動、状態は$q_0$のまま)
- $\delta(q_0, B) = (q_f, B, S)$ (Bを読んだらBを書き、移動なし、状態$q_f$へ遷移して停止)
- その他の遷移は定義しない（または定義しない遷移で停止するよう設計）。
シミュレーターでの動作:
入力テープ 0101B... を与えてこのマシンをシミュレーターで実行すると、以下のステップを追うことができます。
- 初期状態: 状態 $q_0$, ヘッドはテープ左端の
0を指す。テープ:[0]101B... - $\delta(q_0, 0) = (q_0, 0, R)$ に従い、テープは変わらずヘッドが右へ移動。状態 $q_0$, ヘッドは
1を指す。テープ:0[1]01B... - $\delta(q_0, 1) = (q_0, 1, R)$ に従い、テープは変わらずヘッドが右へ移動。状態 $q_0$, ヘッドは
0を指す。テープ:01[0]1B... - $\delta(q_0, 0) = (q_0, 0, R)$ に従い、テープは変わらずヘッドが右へ移動。状態 $q_0$, ヘッドは
1を指す。テープ:010[1]B... - $\delta(q_0, 1) = (q_0, 1, R)$ に従い、テープは変わらずヘッドが右へ移動。状態 $q_0$, ヘッドは
Bを指す。テープ:0101[B]... - $\delta(q_0, B) = (q_f, B, S)$ に従い、テープは変わらずヘッドは移動なし。状態 $q_f$ へ遷移。テープ:
0101[B]... - 状態が受理状態 $q_f$ になったため、マシンは停止します。
このように、すべての入力記号を処理した後、テープの末尾を示す空白記号 B を読み取って停止状態に遷移することで、このマシンは常に有限の時間で計算を終了します。シミュレーターでは、「停止しました (受理状態に到達)」のようなメッセージが表示されるでしょう。
停止しないチューリングマシンの例：無限ループ
次に、意図的に停止しないチューリングマシンの例を考えてみましょう。例えば、「開始状態から右へ移動し続け、何もせず常に同じ状態に戻る」というマシンです。
マシンの仕様例:
- 状態 $Q = {q_0}$ (受理状態なし)
- テープアルファベット $\Sigma = {0, 1, B}$
- 開始状態 $q_0$
- 受理状態 $F = \emptyset$
- 遷移関数 $\delta$:
- $\delta(q_0, 0) = (q_0, 0, R)$
- $\delta(q_0, 1) = (q_0, 1, R)$
- $\delta(q_0, B) = (q_0, B, R)$
シミュレーターでの動作:
入力テープ 0101B... を与えてこのマシンをシミュレーターで実行すると、以下のステップを追うことができます。
- 初期状態: 状態 $q_0$, ヘッドはテープ左端の
0を指す。テープ:[0]101B... - $\delta(q_0, 0) = (q_0, 0, R)$ に従い、状態 $q_0$ のままヘッドが右へ移動。テープ:
0[1]01B... - $\delta(q_0, 1) = (q_0, 1, R)$ に従い、状態 $q_0$ のままヘッドが右へ移動。テープ:
01[0]1B... - $\delta(q_0, 0) = (q_0, 0, R)$ に従い、状態 $q_0$ のままヘッドが右へ移動。テープ:
010[1]B... - $\delta(q_0, 1) = (q_0, 1, R)$ に従い、状態 $q_0$ のままヘッドが右へ移動。テープ:
0101[B]... - $\delta(q_0, B) = (q_0, B, R)$ に従い、状態 $q_0$ のままヘッドが右へ移動。テープ:
0101B[B]... - 以降、マシンは常に空白記号
Bを読み取り、状態 $q_0$ のまま右へ移動し続けます。テープは無限に右に伸びていると仮定されているため、ヘッドは永遠に右へ移動し続け、受理状態に到達することも、遷移が定義されていない状態になることもありません。
このマシンは無限に動作を続けるため、停止しません。シミュレーターでは、ステップ数が際限なく増え続け、停止のメッセージが表示されないことで非停止を確認できます。特定のステップ数でタイムアウトするように設定されているシミュレーターであれば、実行が中断されることになります。
別の停止しない例として、二つの状態 $q_a, q_b$ を持ち、常に互いの状態を行き来しながら同じテープ記号を読み取り、同じ場所に留まるような遷移を持つマシンも考えられます。例: $\delta(q_a, 0) = (q_b, 0, S)$、$\delta(q_b, 0) = (q_a, 0, S)$。ヘッドが0を指している限り、この二つの遷移を無限に繰り返します。これは無限ループの一種です。
停止性と計算可能性：停止問題への示唆
チューリングマシンが停止するかしないかという問題は、「停止問題 (Halting Problem)」として知られ、計算理論において非常に重要な位置を占めています。停止問題とは、「任意のチューリングマシンと任意の入力が与えられたとき、そのマシンがその入力に対して停止するかどうかを判定する万能アルゴリズムは存在するか？」という問題です。
アラン・チューリングは、このような万能アルゴリズムは存在しないことを証明しました。つまり、すべてのチューリングマシンとすべての入力の組み合わせについて、それが停止するかどうかを常に正確に判定できる単一のチューリングマシン（またはアルゴリズム）は構築不可能であるということです。
この決定不能性は、計算の限界を示す基本的な結果であり、現代のコンピュータ科学にも深く関わっています。
もちろん、個別の、比較的単純なチューリングマシンであれば、その遷移規則や構造を分析することで、特定の入力やあるいは全ての入力に対して停止するかどうかを人間が判断することは可能です。本記事で紹介した例のように、停止するものも停止しないものも、その動作原理を理解すれば予測できます。シミュレーターは、このような個別のマシンの動作を具体的に観察し、停止性に関する直感を養うための強力なツールとなります。
シミュレーターでの停止・非停止の観察
サイトのチューリングマシンシミュレーターを利用することで、上で解説したような停止するマシンと停止しないマシンの動作を実際に観察できます。
- 停止するマシンの観察: 遷移表を設定し、入力を与えて実行します。ステップ実行で動作を一つずつ確認すると、どの遷移規則によって状態が変化し、ヘッドが移動するかが分かります。計算が正常に終了した場合、シミュレーターは最終状態（受理状態など）を表示し、「停止しました」といったメッセージとともに停止するはずです。
- 停止しないマシンの観察: 同様に遷移表と入力を設定して実行します。計算が停止しない場合、シミュレーターはステップ実行を続けるか、高速実行であればいつまでも終了しないように見えます。特に無限ループの場合、状態、ヘッド位置、テープの内容のパターンが繰り返されることに気づくでしょう。シミュレーターにステップ数の上限設定があれば、その上限に達した時点で強制的に中断されることもあります。
シミュレーターを用いることで、理論上の概念である「停止」や「非停止」が、実際の機械の動作としてどのように現れるのかを視覚的に捉えることができ、より深い理解につながります。様々な遷移規則を持つマシンを試してみて、どのような場合に停止し、どのような場合に停止しないのかを探求してみてください。
まとめ
チューリングマシンの停止性は、計算が完了するかどうかという、計算理論における最も基本的な性質の一つです。計算が停止することは、有限の時間内に結果が得られることを保証しますが、すべてのチューリングマシンがすべての入力に対して停止するわけではありません。
本記事では、入力テープ全体をスキャンして停止する単純なマシンを例に「停止」の動作を、無限に右移動し続けるマシンを例に「停止しない」動作を解説しました。これらの異なる挙動は、シミュレーターを用いることで具体的に観察でき、チューリングマシンの理論と実践を結びつける手助けとなります。
また、すべてのチューリングマシンが停止するかどうかを常に判定できない「停止問題」に触れ、停止性の概念が計算の限界とも深く関連していることを示唆しました。
シミュレーターを活用し、様々なチューリングマシンを設計してその動作を観察することで、停止性を含むチューリングマシンの計算能力や限界について、より実践的な理解を深めていただければ幸いです。