チューリングマシンによる文字列比較：等価判定のシミュレーター解説
チューリングマシンは、計算の可能性と限界を探求するための理論的なモデルです。非常に単純な構成要素でありながら、現代のコンピュータが行うほとんど全ての計算を実行できる能力を持っています。この能力を具体的に理解するためには、抽象的な定義だけでなく、特定の課題を解決するチューリングマシンの具体的な動作を追うことが有効です。本記事では、与えられた2つの文字列が等しいか（等価であるか）を判定するチューリングマシンを設計し、その動作をシミュレーターで追う方法を解説します。
文字列比較問題の定義
ここで扱う文字列比較問題は、以下のように定義します。
テープ上に、2つの文字列 $w_1$ と $w_2$ が、特殊な区切り記号（例えば #）によって連結された形式 $w_1 # w_2$ で与えられます。チューリングマシンは、この入力テープを読み込み、$w_1$ と $w_2$ が完全に一致する場合に受理状態（例えば halt-accept）へ遷移し、一致しない場合に拒否状態（例えば halt-reject）へ遷移することを目指します。入力文字列は、例えばアルファベット ${0, 1}$ を含むとします。
アルゴリズムの基本戦略
文字列 $w_1$ と $w_2$ を比較するための基本的な戦略は、一文字ずつ対応する位置の文字を比較していくことです。$w_1$ の先頭から順に文字を取り出し、$w_2$ の先頭から順に対応する文字と比較します。
具体的には、以下の手順を繰り返します。
- $w_1$ のまだ比較していない最も左の文字を探します。
- その文字を特別な記号（例えば
X）に置き換えて「比較済み」であることをマークします。 - テープヘッドを右に移動し、区切り記号
#を越えて、$w_2$ のまだ比較していない最も左の文字を探します。 - その文字を特別な記号（例えば
Y）に置き換えて「比較済み」であることをマークします。 - マークする前に読み込んだ $w_1$ の文字と $w_2$ の文字が一致するかを確認します。
- 一致した場合、テープヘッドを左に戻し、手順1に戻ります。
- 一致しなかった場合、2つの文字列は等しくないと判定し、拒否状態へ遷移します。
このプロセスを、$w_1$ または $w_2$ の文字がすべて比較済みになるまで続けます。全ての文字が比較済みになった後、$w_1$ と $w_2$ の長さが等しいことを確認する必要があります。これは、$w_1$ と $w_2$ の全ての文字がそれぞれ X と Y に置き換えられていることを確認することで行えます。
チューリングマシンの構成要素設計
このアルゴリズムを実現するために、チューリングマシンの構成要素を設計します。
- 状態 (States): 文字列 $w_1$ の文字を読んでいる状態、それをマークして $w_2$ の対応する文字を探しに行く状態、$w_2$ の文字を読んでいる状態、それをマークして比較する状態、比較結果に基づいて次の動作を決める状態、そして最終的な受理状態と拒否状態などが必要です。例えば、
q_start(初期状態),q_find_w1_char($w_1$ の比較すべき文字を探す),q_mark_w1($w_1$ の文字をマーク),q_find_w2_char($w_2$ の比較すべき文字を探す),q_mark_w2($w_2$ の文字をマーク),q_compare(文字を比較),q_return_to_w1($w_1$ に戻る),q_check_end(比較終了後の最終チェック),halt-accept,halt-rejectなどが考えられます。 - アルファベット (Alphabet): 入力アルファベット ${0, 1, #}$ に加え、ブランク記号 $\text{B}$、そして比較済みのマークに使用する記号 ${X, Y}$ がテープアルファベットに含まれます。
- 遷移関数 (Transition Function): 各状態とテープから読み込んだ記号のペアに対して、次に遷移する状態、テープに書き込む記号、ヘッドの移動方向（左
L、右R、停止S）を定めます。これがアルゴリズムの各ステップを定義します。
遷移関数設計の例（一部抜粋）
具体的な遷移関数の例を考えます。入力テープは 01#01 とします。初期状態は q_start、ヘッドは一番左にあります。
(q_start, 0)->(q_mark_w1, X, R): $w_1$ の最初の文字0を読み込み、Xに置き換え、右へ移動し$w_1$の文字をマークする状態へ遷移します。テープはX1#01。(q_mark_w1, 1)->(q_mark_w1, 1, R): まだ#ではないので右へ移動。テープはX1#01。(q_mark_w1, #)->(q_find_w2_char, #, R): 区切り記号#を読み込み、#はそのままに、右へ移動し$w_2$の文字を探す状態へ遷移します。テープはX1#01。(q_find_w2_char, 0)->(q_mark_w2, Y, R): $w_2$ の最初の文字0を読み込み、Yに置き換え、右へ移動し$w_2$の文字をマークする状態へ遷移します。マークする前の文字は0です。テープはX1#Y1。(q_mark_w2, 1)->(q_mark_w2, 1, R): まだブランクではないので右へ移動。(q_mark_w2, B)->(q_compare, B, L): ブランクを読み込み、$w_2$ の終端に達したと判断。ブランクはそのままに、左へ移動し比較状態へ遷移します。比較すべき文字は、q_mark_w1で読み込んだ0とq_mark_w2で読み込んだ0です。(q_compare, 1)->(q_compare, 1, L): まだ$w_2$のマークYに達していないので左へ移動。(q_compare, Y)->(q_return_to_w1, Y, L): $w_2$ の比較済みマークYに達しました。ここで、マークする前に読み込んだ $w_1$ の文字 (0) と $w_2$ の文字 (0) が一致するかを内部的に確認します。一致した場合、$Y$ はそのままに、左へ移動し$w_1$に戻る状態へ遷移します。一致しない場合はhalt-rejectへ遷移する規則が必要です（例えば(q_compare, Y)で一致しない場合の遷移を定義）。今回は一致したとします。テープはX1#Y1。(q_return_to_w1, #)->(q_return_to_w1, #, L): 左へ移動。(q_return_to_w1, 1)->(q_return_to_w1, 1, L): 左へ移動。(q_return_to_w1, X)->(q_find_w1_char, X, R): $w_1$ の比較済みマークXに達しました。これは前回の比較が終了した位置です。$X$ はそのままに、右へ移動し、$w_1$ の次の比較すべき文字を探す状態へ遷移します。テープはX1#Y1。
このプロセスを、$w_1$ と $w_2$ の全ての文字が比較されるまで繰り返します。最終的に、$w_1$ と $w_2$ の全ての文字がそれぞれ X と Y に置き換えられ、かつ $w_1$ の終端（# の直前の $X$）、そして $w_2$ の終端（B の直前の $Y$）に達した場合、両方の文字列が完全に一致し、長さも等しいと判断して halt-accept 状態へ遷移します。途中で文字が一致しない、あるいは一方の文字列が他方より先に終端に達した場合は halt-reject へ遷移します。
シミュレーターでの動作追跡
設計したチューリングマシンをシミュレーターに入力し、具体的な文字列（例: 01#01, 01#10, 0#00）を入力として実行することで、上記アルゴリズムがどのように動作するかを視覚的に確認できます。
シミュレーター上では、以下の要素に注目してください。
- テープ表示: 各ステップでテープの内容（記号の書き換え、ブランク含む）がどのように変化するかを確認できます。
XやYが出現し、元の入力記号が上書きされていく様子が分かります。 - ヘッド位置: 現在ヘッドがテープ上のどの位置を指しているかが表示されます。左 (
L) または右 (R) への移動がどのように行われるかを確認できます。 - 現在の状態: マシンの現在の内部状態が表示されます。例えば、
q_find_w1_charやq_compareといった状態名が表示され、アルゴリズムのどの段階にいるのかを把握できます。 - 適用された遷移規則: 現在の状態とヘッド下の記号に基づいて、どの遷移規則
(現在の状態, 読み込んだ記号) -> (次の状態, 書き込む記号, ヘッド移動方向)が適用されたかが表示されます。これにより、なぜそのステップでそのような動作が行われたのかを明確に理解できます。
例えば、入力 01#01 に対してシミュレーターを実行すると、ヘッドが左右を行き来しながら 0 を X に、対応する 0 を Y に置き換え、次に 1 を X に、対応する 1 を Y に置き換える一連の動作が追跡できます。最終的に全ての文字が比較され、テープが XY#XY となり、ヘッドが終端に達した後に halt-accept へ遷移する様子を確認できるはずです。
一方、入力 01#10 の場合、最初の 0 は X に、1 は Y に置き換えられますが、比較段階で 0 と 1 が一致しないため、halt-reject 状態へ遷移する動作が確認できます。
シミュレーターを使うことで、抽象的な遷移規則の集まりが、具体的なテープ上の操作や状態変化として実現される過程をステップバイステップで確認でき、チューリングマシンの動作原理やアルゴリズムの実装方法に対する理解を深めることができます。
まとめ
本記事では、チューリングマシンを用いて2つの文字列の等価性を判定する問題を取り上げ、その基本的なアルゴリズムと、アルゴリズムをチューリングマシンの遷移規則としてどのように設計するかを解説しました。さらに、設計したチューリングマシンの動作をシミュレーターで追跡することの重要性とその方法を示しました。
チューリングマシンの学習においては、理論的な定義を学ぶことに加え、このように具体的な問題を解決するチューリングマシンを設計し、シミュレーターでその動作を確認することが、計算モデルとしてのチューリングマシンの能力と限界を肌で理解するための非常に効果的な方法となります。ぜひ、本記事で解説した文字列比較の例を参考に、ご自身でシミュレーターを用いた学習に取り組んでみてください。