チューリングマシンシミュレーター＆解説

チューリングマシンによる `a^n b^n` 形式文字列の認識：シミュレーターで追う動作ステップ

Tags: チューリングマシン, 言語認識, 計算可能性理論, オートマトン, シミュレーター

はじめに

計算機科学において、言語の認識能力は重要なテーマです。特に、あるクラスの言語を認識できるか否かは、計算モデルの能力を示す指標となります。有限オートマトンは非常にシンプルな計算モデルですが、テープのような記憶媒体を持たないため、文脈自由言語の一部を認識できません。その代表的な例が、aがn個続き、その後にbがn個続く形式の文字列からなる言語 { a^n b^n | n >= 0 } です（例: "", "ab", "aabb", "aaabbb", ...）。

この a^n b^n 形式の文字列を認識するには、「aの個数とbの個数が一致しているか」を記憶し、照合する必要があります。チューリングマシンはテープという記憶媒体を持つため、このような処理が可能です。

本記事では、チューリングマシンがどのようにして a^n b^n 形式の文字列を認識するのか、その基本的なアルゴリズムと状態遷移を解説します。そして、シミュレーター上でその動作をステップバイステップで追体験することで、理論的な仕組みと具体的な機械の動作との対応を深く理解することを目的とします。

a^n b^n 言語の定義とチューリングマシンの役割

a^n b^n 言語とは、アルファベット {a, b} 上の文字列で、0個以上の a の並びの直後に、それと同数の b の並びが続くものです。形式的に { a^n b^n | n >= 0 } と定義されます。

有限オートマトンは入力文字列を一度だけ順方向に読むだけで、過去に読んだ記号の「個数」を正確に記憶し続けることはできません。状態数は有限であるため、任意の数の a を数えることは原理的に不可能です。

一方、チューリングマシンは無限のテープを持ち、ヘッドを左右に移動させてテープ上の記号を読み書きできます。この能力を利用することで、入力文字列を複数回走査したり、テープ上の記号を書き換えて目印をつけたりすることが可能となり、a と b の個数を照合する処理を実現できます。

a^n b^n 認識アルゴリズムの概要

チューリングマシンで a^n b^n 形式の文字列を認識する基本的なアルゴリズムは、以下のような手順で実現できます。

  1. テープの入力文字列を左から右へ走査し、まだ処理していない最初の a を探します。
  2. 最初の a を見つけたら、その a を別の記号（例: X）に書き換えます。これは、「この a は処理済みである」という目印になります。
  3. ヘッドを左方向に戻し、処理済みの a に対応する最初の b を探します。
  4. 最初の b を見つけたら、その b を別の記号（例: Y）に書き換えます。これは、「この b は処理済みであり、対応する a が存在した」という目印になります。
  5. ヘッドを左方向に戻し、まだ処理していない次の a を探すために、先頭（または処理済みの X の直後）に戻ります。
  6. 上記の手順1〜5を、処理すべき a または b がなくなるまで繰り返します。
  7. 全ての a と b を X と Y に置き換え終わった後、テープ上に X と Y 以外の入力記号（a や b）が残っていないか確認します。残りが全て X と Y、そして右側に広がる空白だけであれば、入力文字列は a^n b^n 形式であり、チューリングマシンは受理状態へ遷移して停止します。それ以外の場合は非受理となります。

このアルゴリズムでは、a を1つ処理するたびにそれに対応する b を1つ処理するというサイクルを繰り返すことで、最終的に a と b の個数が一致しているかどうかを確認しています。テープへの書き換えとヘッドの往復移動が、この「対応付け」と「個数の一致確認」を可能にしています。

シミュレーターで追う具体的な動作ステップ

それでは、具体的な入力文字列 aabb を例に、上記のアルゴリズムに基づくチューリングマシンの動作をシミュレーター上で追ってみましょう。チューリングマシンは以下の状態と遷移ルールを持つとします。初期状態は q_start、受理状態は q_accept、非受理状態は q_reject とします。テープの空白記号は _ とします。

状態と遷移ルール

入力: aabb での動作追跡

  1. 初期状態: 状態 q_start、テープ ... _ [a] a b b _ ...、ヘッドは最初の a の位置。
    • シミュレーター表示例: State: q_start, Tape: ... _ [a] a b b _ ... (括弧はヘッド位置)
  2. ステップ 1: State: q_start, Head: a. Rule: a -> X, R, q_find_b.
    • 動作: a を X に書き換え、ヘッド右移動、状態 q_find_b。
    • シミュレーター: State: q_find_b, Tape: ... _ X [a] b b _ ...
  3. ステップ 2: State: q_find_b, Head: a. Rule: a -> a, R, q_find_b.
    • 動作: ヘッド右移動、状態 q_find_b のまま。
    • シミュレーター: State: q_find_b, Tape: ... _ X a [b] b _ ...
  4. ステップ 3: State: q_find_b, Head: b. Rule: b -> Y, L, q_find_x.
    • 動作: b を Y に書き換え、ヘッド左移動、状態 q_find_x。
    • シミュレーター: State: q_find_x, Tape: ... _ X [a] Y b _ ...
  5. ステップ 4: State: q_find_x, Head: a. Rule: a -> a, L, q_find_x.
    • 動作: ヘッド左移動、状態 q_find_x のまま。
    • シミュレーター: State: q_find_x, Tape: ... _ [X] a Y b _ ...
  6. ステップ 5: State: q_find_x, Head: X. Rule: X -> X, R, q_start.
    • 動作: ヘッド右移動、状態 q_start。次の a を探すサイクルへ。
    • シミュレーター: State: q_start, Tape: ... _ X [a] Y b _ ...
  7. ステップ 6: State: q_start, Head: a. Rule: a -> X, R, q_find_b.
    • 動作: a を X に書き換え、ヘッド右移動、状態 q_find_b。
    • シミュレーター: State: q_find_b, Tape: ... _ X X [Y] b _ ...
  8. ステップ 7: State: q_find_b, Head: Y. Rule: Y -> Y, R, q_find_b.
    • 動作: ヘッド右移動、状態 q_find_b のまま。
    • シミュレーター: State: q_find_b, Tape: ... _ X X Y [b] _ ...
  9. ステップ 8: State: q_find_b, Head: b. Rule: b -> Y, L, q_find_x.
    • 動作: b を Y に書き換え、ヘッド左移動、状態 q_find_x。
    • シミュレーター: State: q_find_x, Tape: ... _ X X [Y] Y _ ...
  10. ステップ 9: State: q_find_x, Head: Y. Rule: Y -> Y, L, q_find_x.
    • 動作: ヘッド左移動、状態 q_find_x のまま。
    • シミュレーター: State: q_find_x, Tape: ... _ X [X] Y Y _ ...
  11. ステップ 10: State: q_find_x, Head: X. Rule: X -> X, R, q_start.
    • 動作: ヘッド右移動、状態 q_start。次の a を探すサイクルへ。
    • シミュレーター: State: q_start, Tape: ... _ X [X] Y Y _ ...
  12. ステップ 11: State: q_start, Head: X. Rule: X -> X, R, q_start.
    • 動作: ヘッド右移動、状態 q_start のまま。
    • シミュレーター: State: q_start, Tape: ... _ X X [Y] Y _ ...
  13. ステップ 12: State: q_start, Head: Y. Rule: Y -> Y, R, q_check_all_y.
    • 動作: ヘッド右移動、状態 q_check_all_y。a の処理が終わり、残りが Y だけか確認へ。
    • シミュレーター: State: q_check_all_y, Tape: ... _ X X Y [Y] _ ...
  14. ステップ 13: State: q_check_all_y, Head: Y. Rule: Y -> Y, R, q_check_all_y.
    • 動作: ヘッド右移動、状態 q_check_all_y のまま。
    • シミュレーター: State: q_check_all_y, Tape: ... _ X X Y Y [_] ...
  15. ステップ 14: State: q_check_all_y, Head: _. Rule: _ -> _, R, q_accept.
    • 動作: ヘッド右移動、状態 q_accept。受理。
    • シミュレーター: State: q_accept, Tape: ... _ X X Y Y _ [_] ...

このように、入力 aabb は定義された遷移ルールに従って q_accept 状態に到達するため、受理されます。

非受理となる例: aab での動作追跡

入力 aab の場合、同様の手順で最初の2つの a は X に、最初の1つの b は Y に置換されます。テープが ... _ X X Y [_] ... となった後、ヘッドは _ に、状態は q_check_all_y に達します。

  1. ... ステップ 8 まで同様、テープ ... _ X X Y [b] _ ...、状態 q_find_b
    • シミュレーター: State: q_find_b, Tape: ... _ X X Y [b] _ ...
  2. ステップ 9: State: q_find_b, Head: _. Rule: _ -> _, R, q_reject. (入力 aab ではステップ8で b ではなく _ に到達)
    • 動作: ヘッド右移動、状態 q_reject。非受理。
    • シミュレーター: State: q_reject, Tape: ... _ X X Y _ [_] ...

このように、a に対応する b が見つからずにテープの終端に到達した場合など、正しくない形式の入力は q_reject 状態に遷移し、非受理となります。シミュレーターを用いることで、このような非受理となるケースの動作も詳細に確認できます。

シミュレーターと理論の対応

シミュレーターの画面上では、通常、以下の要素が表示されます。

理論的なチューリングマシンの定義における「状態」「アルファベット」「遷移関数」「テープ」「ヘッド」といった要素が、シミュレーターのこれらの表示要素と直接的に対応しています。シミュレーターの「ステップ実行」機能は、現在の状態とヘッド下の記号に基づき、遷移関数に従って次の状態、テープへの書き込み、ヘッドの移動を実行する過程を忠実に再現します。

例えば、ステップ実行時に状態が q_find_b でヘッド下の記号が b であった場合、シミュレーターは状態遷移図の中から q_find_b ノードから出ていて、ラベルが b / Y, L のエッジを探し出し、それに従ってテープ上の b を Y に書き換え、ヘッドを左に一つ移動させ、現在の状態をそのエッジが指す先の状態（q_find_x）に変更します。この一連の動作がシミュレーター画面上で視覚的に確認できるのです。

まとめ

本記事では、チューリングマシンが { a^n b^n | n >= 0 } 形式の文字列を認識する仕組みについて解説しました。有限オートマトンでは困難なこのタスクが、チューリングマシンが持つテープという記憶媒体とヘッドの往復移動能力によって実現できることを示しました。

具体的なアルゴリズムとしては、a と b を対応付けながら順に処理済みマークに書き換え、最後に残りが全て処理済みマークと空白のみかを確認するという手順を踏みます。この過程における状態遷移、テープの内容変化、ヘッドの移動といったチューリングマシンの詳細な動作は、シミュレーターを用いることで視覚的に追跡し、理解を深めることが可能です。

計算機科学を学ぶ上で、理論上の計算モデルと具体的な動作の繋がりを理解することは非常に重要です。ぜひシミュレーターを活用し、様々な入力文字列を与えて動作を観察することで、チューリングマシンの能力と限界についての理解を一層深めてください。