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

チューリングマシンで有限オートマトンを模倣する：`(ab)*` 言語認識を例に

はじめに

計算機科学において、有限オートマトン（Finite State Automaton, FSA）は最も基本的な計算モデルの一つです。限られたメモリ（状態）を持ち、入力ストリームを一度だけ読んで言語を認識します。一方、チューリングマシンは無限のテープを持ち、ヘッドを左右に動かし、テープの内容を書き換える能力を持つ、より強力な計算モデルです。

本記事では、チューリングマシンがいかにして有限オートマトンを模倣できるのか、具体的な例を通して解説します。特に、比較的単純な正規言語である(ab)*（「ab」が0回以上繰り返される文字列、例: "", "ab", "abab", "ababab", ...）を認識する有限オートマトンの動作を、対応するチューリングマシンがどのように実現するかを、シミュレーターでの動作を追跡しながら詳細に見ていきます。

この解説を通して、チューリングマシンの基本的な動作原理を再確認するとともに、より強力な計算モデルがどのようにしてより単純なモデルの能力を包含するのかを理解することが目的です。

有限オートマトン（FSA）とは

有限オートマトンは、以下の要素で形式的に定義されます。

• 状態集合 (Q): オートマトンが取りうる有限個の状態の集合。
• 入力アルファベット (Σ): 入力として許される記号の有限集合。
• 遷移関数 (δ): 現在の状態と入力記号から、次の状態を決定する関数。δ: Q × Σ → Q.
• 初期状態 (q₀): 計算開始時の状態。q₀ ∈ Q.
• 受理状態集合 (F): 入力文字列の処理が終了したときに、オートマトンがこれらの状態の一つにあれば、入力文字列は受理されます。F ⊆ Q.

FSAは、入力文字列を左から右へ1記号ずつ読み込み、現在の状態と読み込んだ記号に応じて定義された遷移関数に従って状態を変化させていきます。全ての入力記号を読み終えた後、最終状態が受理状態であれば、その入力文字列はFSAによって認識された（受理された）と判断されます。

(ab)* を認識するFSAの例

正規表現(ab)*によって定義される言語を認識する簡単なDFA（決定性有限オートマトン）を考えてみましょう。この言語は空文字列 ε、"ab", "abab", "ababab", ... といった文字列を含みます。

この言語を認識するFSAは、例えば以下のような状態と遷移で構成できます。

• 状態: q0 (初期状態), q1, q2 (受理状態)
• 入力アルファベット: {a, b}
• 遷移関数:
  • δ(q0, a) = q1
  • δ(q1, b) = q2
  • δ(q2, a) = q1
  • δ(q0, b) は遷移なし（拒否）
  • δ(q1, a) は遷移なし（拒否）
  • δ(q2, b) は遷移なし（拒否）
• 初期状態: q0
• 受理状態集合: {q2} (注: 空文字列εを受理するためには、初期状態q0も受理状態に含める必要がありますが、ここでは説明を単純化するため、非空文字列の(ab)*に焦点を当て、q0を受理状態から除外します。多くのFSA定義ではεも考慮します。後述のTM設計では、ε入力（空テープ）は拒否される設計とします。)

このFSAの動作イメージは以下のようになります。

• 初期状態 q0 から開始。
• 'a' を読むと q1 へ。
• q1 で 'b' を読むと q2 へ。これで "ab" を1セット認識したことになります。
• q2 で 'a' を読むと再び q1 へ。次の "ab" セットの 'a' を待つ状態になります。
• q2 で 'b' を読むと遷移がなくなり、拒否となります。
• q0 で 'b' を読む、q1 で 'a' を読む場合も同様に拒否となります。
• 入力文字列を全て読み終えたとき、状態が q2 であれば受理、それ以外の状態であれば拒否となります。

例えば、入力 "abab" の場合： q0 ->(a)-> q1 ->(b)-> q2 ->(a)-> q1 ->(b)-> q2 。終端記号を読んだ際にq2なので受理。 入力 "aba" の場合： q0 ->(a)-> q1 ->(b)-> q2 ->(a)-> q1 。終端記号を読んだ際にq1なので拒否。

チューリングマシンによるFSAシミュレーションの考え方

チューリングマシンがFSAの動作を模倣するには、以下の要素を対応させます。

1. FSAの状態 ↔ チューリングマシンの状態: FSAの各状態（q0, q1, q2, ...）は、対応するチューリングマシンの状態（Q0, Q1, Q2, ...）として表現されます。チューリングマシンには通常、初期状態、受理状態、拒否状態など特別な状態があります。FSAの受理状態は、チューリングマシンの受理状態への遷移と関連付けられます。
2. FSAの入力テープ ↔ チューリングマシンのテープ: FSAが入力ストリームを読むように、チューリングマシンはテープ上の入力記号を読みます。FSAは通常入力を左から右へ一度だけ読み進めます。チューリングマシンはヘッドを常に右に移動させることで、このFSAの動作を模倣します。
3. FSAの遷移関数 ↔ チューリングマシンの遷移関数: FSAの遷移関数 δ(現在の状態, 入力記号) = 次の状態 は、チューリングマシンの遷移関数 δ_TM(現在の状態, 読み取った記号) = (次の状態, 書き込む記号, ヘッドの移動方向) に対応させます。FSAはテープに書き込みませんが、チューリングマシンでは読み取った記号をそのまま書き戻す動作を行います。ヘッドの移動方向は常に右（R）とします。
4. FSAの受理 ↔ チューリングマシンの受理: FSAが全ての入力を読み終えて受理状態にいる場合、対応するチューリングマシンも入力テープの終端（通常は空白記号 ' '）を読み込んだときに、FSAの受理状態に対応するチューリングマシンの状態からチューリングマシンの受理状態へ遷移するように設計します。

つまり、FSAシミュレーションを行うチューリングマシンは、以下の特徴を持つ非常に単純なものになります。

• テープへの書き込みは実質行わない（読み取った記号をそのまま書き戻す）。
• ヘッドの移動方向は常に右。
• テープの左端境界を考慮する必要がない（右へ進むだけなので）。

このような制約をかけることで、チューリングマシンの動作は有限オートマトンの動作と等価になります。これは、チューリングマシンがFSAよりも強力な計算能力を持つことの一つの側面を示しています。

(ab)* を認識するチューリングマシンの設計

前述の(ab)* を認識するFSAを模倣するチューリングマシンを設計します。

チューリングマシンの構成要素:

• 状態集合 Q_TM: { Q0, Q1, Q2, Q_accept, Q_reject }
  • Q0: FSAのq0に対応する状態 (初期状態)
  • Q1: FSAのq1に対応する状態
  • Q2: FSAのq2に対応する状態
  • Q_accept: チューリングマシンの受理状態
  • Q_reject: チューリングマシンの拒否状態
• テープアルファベット Γ: { a, b, ' ' } (' ' は空白記号)
• 入力アルファベット Σ_TM: { a, b }
• 初期状態 q_init: Q0
• 受理状態 q_accept: Q_accept
• 遷移関数 δ_TM(現在の状態, 読み取った記号) = (次の状態, 書き込む記号, ヘッドの移動方向):
  • (ab)* のパターン認識部分（FSAの遷移に対応）：
    • δ_TM(Q0, a) = (Q1, a, R) # FSA: q0 --a--> q1
    • δ_TM(Q1, b) = (Q2, b, R) # FSA: q1 --b--> q2
    • δ_TM(Q2, a) = (Q1, a, R) # FSA: q2 --a--> q1
  • パターンに合わない場合の処理（FSAで遷移がない場合に対応）：
    • δ_TM(Q0, b) = (Q_reject, b, R) # q0 で 'b' は不正
    • δ_TM(Q1, a) = (Q_reject, a, R) # q1 で 'a' は不正
    • δ_TM(Q2, b) = (Q_reject, b, R) # q2 で 'b' は不正
  • 入力テープの終端処理（空白記号 ' ' を読んだ場合）：
    • δ_TM(Q0, ' ') = (Q_reject, ' ', R) # 初期状態で終端 => 空文字列だが、今回の設計ではεは拒否
    • δ_TM(Q1, ' ') = (Q_reject, ' ', R) # 'a' で終わった後に終端 => 拒否
    • δ_TM(Q2, ' ') = (Q_accept, ' ', R) # 'ab' の繰り返しパターンの終端で終端 => 受理
  • Q_accept および Q_reject 状態からは遷移を定義しません。これらの状態に到達するとマシンは停止します。

この遷移関数を状態遷移図で示すと、FSAの状態遷移図に停止状態への遷移と終端記号の処理が追加された形になります。シミュレーターでは、これらの遷移規則を入力して動作を確認します。

シミュレーターでの動作追跡

それでは、このチューリングマシンを使って、いくつかの入力文字列に対する動作をシミュレーターで追跡してみましょう。

例1: 入力 "ab"

テープ初期状態: [a]b (ヘッドは一番左の 'a' の位置) 現在の状態: Q0

1. (Q0, [a]b ): 現在の状態 Q0, 読み取った記号 'a'。遷移規則 δ_TM(Q0, a) = (Q1, a, R) を適用。

   • 次の状態: Q1
   • 書き込む記号: 'a' (読み取った記号をそのまま書き戻す)
   • ヘッドの移動方向: 右 (R) テープ状態: a[b] 現在の状態: Q1

2. (Q1, a[b] ): 現在の状態 Q1, 読み取った記号 'b'。遷移規則 δ_TM(Q1, b) = (Q2, b, R) を適用。

   • 次の状態: Q2
   • 書き込む記号: 'b'
   • ヘッドの移動方向: 右 (R) テープ状態: ab[ ] 現在の状態: Q2

3. (Q2, ab[ ]): 現在の状態 Q2, 読み取った記号 ' ' (空白)。遷移規則 δ_TM(Q2, ' ') = (Q_accept, ' ', R) を適用。

   • 次の状態: Q_accept
   • 書き込む記号: ' '
   • ヘッドの移動方向: 右 (R) テープ状態: ab [ ] 現在の状態: Q_accept

4. (Q_accept, ab [ ]): 受理状態 Q_accept に到達したため、マシンは停止します。入力 "ab" は受理されました。

例2: 入力 "abab"

テープ初期状態: [a]bab 現在の状態: Q0

1. (Q0, [a]bab ): δ_TM(Q0, a) = (Q1, a, R) -> (Q1, a[b]ab)
2. (Q1, a[b]ab ): δ_TM(Q1, b) = (Q2, b, R) -> (Q2, ab[a]b)
3. (Q2, ab[a]b ): δ_TM(Q2, a) = (Q1, a, R) -> (Q1, aba[b])
4. (Q1, aba[b] ): δ_TM(Q1, b) = (Q2, b, R) -> (Q2, abab[ ])
5. (Q2, abab[ ]): δ_TM(Q2, ' ') = (Q_accept, ' ', R) -> (Q_accept, abab [ ])

受理状態 Q_accept に到達し、停止。入力 "abab" は受理されました。

例3: 入力 "aba"

テープ初期状態: [a]ba 現在の状態: Q0

1. (Q0, [a]ba ): δ_TM(Q0, a) = (Q1, a, R) -> (Q1, a[b]a)
2. (Q1, a[b]a ): δ_TM(Q1, b) = (Q2, b, R) = (Q2, ab[a])
3. (Q2, ab[a] ): δ_TM(Q2, a) = (Q1, a, R) = (Q1, aba[ ])
4. (Q1, aba[ ]): δ_TM(Q1, ' ') = (Q_reject, ' ', R) -> (Q_reject, aba [ ])

拒否状態 Q_reject に到達し、停止。入力 "aba" は拒否されました。これは、FSAが最後にq1で終端記号を読んだ場合と同様です。

例4: 入力 "a"

テープ初期状態: [a] 現在の状態: Q0

1. (Q0, [a] ): δ_TM(Q0, a) = (Q1, a, R) -> (Q1, a[ ])
2. (Q1, a[ ]): δ_TM(Q1, ' ') = (Q_reject, ' ', R) -> (Q_reject, a [ ])

拒否状態 Q_reject に到達し、停止。入力 "a" は拒否されました。これは、FSAがq1で終端記号を読んだ場合と同様です。

例5: 入力 "b"

テープ初期状態: [b] 現在の状態: Q0

1. (Q0, [b] ): δ_TM(Q0, b) = (Q_reject, b, R) -> (Q_reject, b [ ])

拒否状態 Q_reject に到達し、停止。入力 "b" は拒否されました。これは、FSAがq0で'b'を読んで遷移がない場合と同様です。

例6: 入力 "" (空文字列)

テープ初期状態: [ ] 現在の状態: Q0

1. (Q0, [ ]): δ_TM(Q0, ' ') = (Q_reject, ' ', R) -> (Q_reject, [ ])

拒否状態 Q_reject に到達し、停止。入力 "" は拒否されました。今回のFSA/TM設計では、εを受理していません。

シミュレーター上でこれらの入力例を実際に実行し、状態遷移図やテープの状態変化をステップごとに追うことで、理論で学んだFSAの動作が、チューリングマシンの具体的な命令としてどのように実現されているかを視覚的に理解できます。FSAの「状態」がTMの「状態」に、「入力記号の読み取り」がTMの「テープ記号の読み取りとヘッド移動」に、そして「受理」がTMの「受理状態への到達」に対応していることを確認できるでしょう。

まとめ

本記事では、チューリングマシンがいかにして有限オートマトンの動作を模倣できるのかを、具体的な例として正規言語(ab)*を認識するFSAとそれに対応するチューリングマシンの設計を通して解説しました。チューリングマシンは、テープへの書き込みやヘッドの左右移動といった強力な機能を持っていますが、これらを制限することで、有限オートマトンと同等の計算能力を持つマシンとして動作させることが可能です。

有限オートマトンのシミュレーションは、チューリングマシンの能力を理解する上での第一歩となります。FSAはテープを右に一方通行で読むだけで書き込みができないモデルに対応し、これにスタック（無限のメモリをLIFOで利用）の機能を追加したプッシュダウンオートマトン（PDA）は、チューリングマシンのテープをスタックとして利用することでシミュレート可能です。そして、チューリングマシン自身は、他のチューリングマシンの動作をシミュレートできる万能チューリングマシンが存在します。このように、計算モデルの階層構造を具体的なシミュレーション例を通して理解することは、計算理論への理解を深める上で非常に役立ちます。

今回設計したチューリングマシンを本サイトのシミュレーターに入力し、様々な入力文字列でその動作を試してみてください。FSAの状態遷移とTMの動作ステップがどのように対応しているかを、視覚的に確認しながら学習を進めることをお勧めします。