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

チューリングマシンによる文字列連結：シミュレーターで追う実装ステップ

計算機科学の基本的な計算モデルであるチューリングマシンは、一見単純な仕組みに見えますが、様々な計算を行う能力を持っています。本記事では、チューリングマシンがどのようにして二つの文字列を連結するという操作を実現するかを、具体的なアルゴリズムと本サイトのシミュレーターでの動作例を交えて解説します。抽象的な理論だけでなく、それがテープ上での具体的な記号の操作としてどのように実現されるのかを視覚的に追体験することで、チューリングマシンへの理解をより一層深めることができるでしょう。

チューリングマシンによる文字列連結の考え方

文字列の連結とは、例えば文字列S1と文字列S2があるとき、それらを順番に並べて新しい一つの文字列S1S2を作り出す操作です。チューリングマシンでこの操作を行うためには、テープ上の記号を読み取り、ヘッドを移動させ、別の場所に記号を書き込むという基本動作を組み合わせる必要があります。

今回考える文字列連結のシナリオは以下のようになります。

• 入力: テープ上に、二つの文字列S1とS2が空白シンボル（例: #）で区切られて並んでいます。例: #S1#S2# (#は空白シンボル、S1とS2は任意の文字列)。
• 出力: S1の直後にS2が続く形で連結された文字列がテープ上に記述されます。例: #S1S2#。S1とS2の間にあった区切り記号はなくなります。

この操作を実現するためには、文字列S2の各文字を一つずつ読み取り、それを文字列S1の末尾にある空白位置に移動させて書き込むという手順を踏むことになります。チューリングマシンは状態遷移によって「今何をしているか（文字列S1の末尾を探しているのか、S2の文字を読んでいるのか、S1の末尾に書き込んでいるのかなど）」を管理しながら、この作業を進めます。

文字列連結アルゴリズムの概要

文字列 #S1#S2# を #S1S2# に変換するアルゴリズムの基本的な流れは以下のようになります。

1. まず、文字列S1の末尾を見つけます。これは、テープを右方向にスキャンし、文字列S1の最後の文字の直後にある空白シンボル#を見つけることで実現できます。
2. 次に、文字列S1とS2を区切っている空白シンボル#を越え、文字列S2の先頭にヘッドを移動させます。
3. 文字列S2の最初の文字を読み取ります。この文字をどこか別の場所に「記憶」しておく必要がありますが、標準的な単一テープチューリングマシンでは状態のみで記憶できる情報量は限られます。そこで、読み取った文字を一時的に別の記号に置き換えるなどの工夫が必要になる場合があります。あるいは、読み取った文字に対応する状態に遷移することで、間接的に「どの文字を運んでいるか」を表現します。今回は後者のアプローチで説明します。
4. 読み取ったS2の文字を書き込むために、文字列S1の末尾位置までヘッドを戻します。
5. 文字列S1の末尾の空白位置に、S2から読み取った文字を書き込みます。
6. 書き込み後、S2の元の位置に戻り、一時的に置き換えた記号を元の文字に戻します（もし置き換え方式をとる場合）。今回の状態遷移方式では、元のS2の場所に戻る動作を行います。
7. このプロセス（S2の文字を読み取り、S1の末尾に書き込み、S2の元の場所に戻る）を、S2の終端（次の空白シンボル#）に到達するまで繰り返します。
8. S2の終端に達したら、処理を終了（停止状態へ遷移）します。このとき、S1とS2の間にあった空白シンボル#は、S2の文字が書き込まれることで自然に上書きされて消滅するか、あるいは最後にテープを整理するステップが必要になります。シンプルなアルゴリズムでは、上書きによって消滅させることを目指します。

シミュレーターで追う文字列連結の動作例

具体的な入力として、S1=ab、S2=cd とし、初期テープ内容を #ab#cd# とします。空白シンボルは#、アルファベットは {a, b, c, d, #} とします。

以下に、この操作を行うチューリングマシンの状態遷移の例と、それに沿ったシミュレーター上での動作イメージを示します。

• 状態: q0 (初期), q_find_s1_end (S1の末尾を探す), q_goto_s2_start (S2の先頭へ移動), q_read_s2_char_a, q_read_s2_char_b, q_read_s2_char_c, q_read_s2_char_d (S2の文字'a','b','c','d'を読み取り記憶), q_goto_s1_end_for_write_a, q_goto_s1_end_for_write_b, ... (S1の末尾に戻る（運ぶ文字別）), q_write_a, q_write_b, ... (文字を書き込む), q_goto_s2_original_pos_a, q_goto_s2_original_pos_b, ... (S2の元の場所に戻る), q_halt (停止)

動作ステップの例:

1. 初期状態: q0、テープは #ab#cd#、ヘッドは最初の#にあります。
   • 遷移例: (q0, #) -> (q_find_s1_end, #, R) - 空白を読み取り、S1の末尾を探して右へ移動。
2. S1の末尾を探す: q_find_s1_end状態で、a, bを読み取りながら右へ移動。
   • 遷移例: (q_find_s1_end, a) -> (q_find_s1_end, a, R), (q_find_s1_end, b) -> (q_find_s1_end, b, R)
3. S1とS2の間の空白に到達: #abの後の#に到達。
   • 遷移例: (q_find_s1_end, #) -> (q_goto_s2_start, #, R) - S1の末尾の#を読み取り、そのままにしてS2の先頭を探して右へ移動。テープ: #ab#cd#、ヘッドは'c'の上。
4. S2の最初の文字を読み取る: q_goto_s2_start状態でcを読み取る。
   • 遷移例: (q_goto_s2_start, c) -> (q_goto_s1_end_for_write_c, #, L) - cを読み取り、「cを運んでいる」状態(q_goto_s1_end_for_write_c)に遷移。元のcの位置には一時的に空白#を書き込む（これは簡易化のため。実際には他の記号を使うか、戻る際に元の記号を復元する必要がある。シミュレーターでは、一時的な書き換えと復元を表現する必要があるが、今回は読み取った文字を状態として記憶し、元の場所には何も書き込まずに戻る simpler approach を想定する）。 simpler approach であれば、読み取ったシンボルはそのままにヘッドを動かす。
   • Simple Approach: (q_goto_s2_start, c) -> (q_goto_s1_end_for_write_c, c, L) - cを読み取り、そのままにして左へ移動。テープ: #ab#cd#、ヘッドは'c'の上、状態は q_goto_s1_end_for_write_c。
5. S1の末尾に戻る: q_goto_s1_end_for_write_c状態で左へ移動。# (S1の末尾) を探す。
   • 遷移例: (q_goto_s1_end_for_write_c, d) -> (q_goto_s1_end_for_write_c, d, L), (q_goto_s1_end_for_write_c, #) -> (q_write_c, #, R) - #を読み取り、書き込み状態(q_write_c)へ遷移し右へ移動。テープ: #ab#cd#、ヘッドはS1の末尾の#の上、状態は q_write_c。
6. 文字を書き込む: q_write_c状態で空白#を読み取る。
   • 遷移例: (q_write_c, #) -> (q_goto_s2_original_pos, c, R) - cを書き込み、S2の元の場所に戻る状態(q_goto_s2_original_pos)へ遷移し右へ移動。テープ: #abc#d#、ヘッドはdの上。
7. S2の元の場所に戻る: q_goto_s2_original_pos状態で、S2の先頭の次の文字を探して右へ移動。S2の終端#の手前まで移動する。今回はS2がcdなので、dを通過。
   • 遷移例: (q_goto_s2_original_pos, d) -> (q_goto_s2_original_pos, d, R)。テープ: #abc#d#、ヘッドは最後の#の上。
   • Simple Approach Revisit: 元の位置に戻るには、最初にS2の文字を読み取った際に、その場所を何らかの方法でマークする必要がある。あるいは、S2の開始位置から何文字目を読み取ったかを状態として記憶し、S1の末尾に書き込んだ後、S2の開始位置まで戻ってから、記憶した文字数だけ右へ移動するという複雑な手順が必要になる。
   • Alternative Simple Approach (Marker): S2の先頭文字を読み取った際に、その位置に一時的なマーカーXを書き込む。S1の末尾に文字を書き込んだ後、Xまで戻る。Xを元の文字に戻し、右へ移動して次の文字処理へ。
     • q0: #ab#cd# -> (R) -> #ab#cd# ヘッド @ a
     • q_find_s1_end: (R) -> #ab#cd# ヘッド @ # (between ab and cd)
     • (q_find_s1_end, #) -> (q_read_s2, #, R) -> #ab#cd# ヘッド @ c. State: q_read_s2
     • (q_read_s2, c) -> (q_goto_write_c, X, L) - cを読み取り、位置にXを書き込み、「cを運ぶ」状態q_goto_write_cへ。テープ: #ab#Xd# ヘッド @ b.
     • (q_goto_write_c, b) -> (q_goto_write_c, b, L) -> #ab#Xd# ヘッド @ # (after ab)
     • (q_goto_write_c, #) -> (q_write_c, #, R) - S1末尾の#に到達。「cを書き込む」状態q_write_cへ、右へ移動。テープ: #ab#Xd# ヘッド @ # (after ab).
     • (q_write_c, #) -> (q_goto_return, c, R) - cを書き込み、「Xに戻る」状態q_goto_returnへ、右へ移動。テープ: #abcXd# ヘッド @ X.
     • (q_goto_return, X) -> (q_read_s2, c, R) - Xに到達。Xを元のcに戻し、「S2の次の文字を読み取る」状態q_read_s2へ、右へ移動。テープ: #abccd# ヘッド @ d.
     • (q_read_s2, d) -> (q_goto_write_d, X, L) - dを読み取り、位置にXを書き込み、「dを運ぶ」状態q_goto_write_dへ。テープ: #abccX# ヘッド @ c.
     • ... (同様の往復処理でdをS1の末尾に書き込む)
     • (q_write_d, #) -> (q_goto_return, d, R) - dを書き込み。テープ: #abcdX# ヘッド @ X.
     • (q_goto_return, X) -> (q_read_s2, d, R) - Xを元のdに戻し。テープ: #abcddd# ヘッド @ # (after last d).
     • (q_read_s2, #) -> (q_halt, #, N) - S2の終端#に到達。停止状態へ。テープは #abcd# になっているはず（最後のdの後の#は元々存在）。

このマーカーを使った往復方式は、チューリングマシンで文字列連結を実現する一般的な方法です。シミュレーターでは、Xのような一時的な記号を利用することで、この動作を視覚的に追うことができます。

チューリングマシンの形式的定義（例）

上記のマーカー (X) を使用したアルゴリズムに基づく、簡略化された形式的定義の一部を示します。

• 状態集合 Q: {q0, q_find_s1_end, q_read_s2, q_goto_write, q_write, q_goto_return, q_halt} (運ぶ文字ごとにq_goto_write, q_write, q_goto_returnは分岐する)
• アルファベット Σ: {a, b, c, d, #, X} (Xはマーカーとして使用)
• 入力アルファベット Γ: {a, b, c, d, #}
• 空白シンボル B: #
• 開始状態 q0: q0
• 停止状態 F: {q_halt}
• 遷移関数 δ: (一部抜粋)
  • (q0, #) = (q_find_s1_end, #, R)
  • (q_find_s1_end, x) = (q_find_s1_end, x, R) for x in {a, b, c, d}
  • (q_find_s1_end, #) = (q_read_s2, #, R)
  • (q_read_s2, a) = (q_goto_write_a, X, L)
  • (q_read_s2, b) = (q_goto_write_b, X, L)
  • (q_read_s2, c) = (q_goto_write_c, X, L)
  • (q_read_s2, d) = (q_goto_write_d, X, L)
  • (q_read_s2, #) = (q_halt, #, N)
  • (q_goto_write_a, x) = (q_goto_write_a, x, L) for x in {a, b, c, d, #}
  • (q_goto_write_a, #) = (q_write_a, #, R) (S1の末尾の#に到達)
  • (q_write_a, #) = (q_goto_return, a, R) (S1末尾の#に'a'を書き込み、戻る)
  • ... (他の文字 (b, c, d) に対する q_goto_write, q_write 遷移も同様)
  • (q_goto_return, x) = (q_goto_return, x, R) for x in {a, b, c, d, #}
  • (q_goto_return, X) = (q_read_s2, Y, R) (Xを読み取り、元の文字Yに戻す遷移。例: (q_goto_return, X) = (q_read_s2, c, R) if the char was c) - 注: この遷移定義は、どのXがどの元の文字だったかを状態だけで判別できない標準的なチューリングマシンでは直接は書けません。実際には、状態に運んでいる文字の情報を含めるか、より複雑な状態遷移設計が必要です。

より正確な遷移関数の定義は、運んでいる文字を状態名に含めることで表現できます。例: q_goto_write_char_a, q_write_char_a, q_goto_return_char_a のように状態数を増やします。

• (q_read_s2, a) = (q_goto_write_a, X, L) - S2から'a'を読み、'X'に置換、q_goto_write_a状態へ。
• (q_goto_write_a, x) = (q_goto_write_a, x, L) for x in {a, b, c, d, #}
• (q_goto_write_a, #) = (q_write_a, #, R) - S1末尾の#へ。
• (q_write_a, #) = (q_goto_return_a, a, R) - '#'に'a'を書き込み、q_goto_return_a状態へ。
• (q_goto_return_a, x) = (q_goto_return_a, x, R) for x in {a, b, c, d, #}
• (q_goto_return_a, X) = (q_read_s2, a, R) - 'X'に到達。'X'を元の'a'に戻し、次のS2文字読み取りへ。

これらの遷移をシミュレーターに設定することで、上記で解説したステップを実際に実行し、テープ内容の変化やヘッドの動きを確認することができます。

まとめ

本記事では、チューリングマシンがどのようにして文字列の連結という一見簡単な操作を実現するかを解説しました。文字列S2の文字を一つずつ読み取り、S1の末尾に運んで書き込むという往復運動を繰り返すことで、この計算が可能になることが理解できたかと思います。このプロセスでは、チューリングマシンの「状態」が現在のタスク（例: S1の末尾を探している、文字を運んでいる）を記憶し、「テープ」がデータを保持し、「ヘッド」がデータへのアクセスと操作を司るという、チューリングマシンの基本要素が不可欠な役割を果たしています。

シミュレーターを使って、初期テープの内容を変えたり、遷移関数をステップごとに追ったりすることで、チューリングマシンが具体的な計算を行う仕組みについての理解をさらに深めることができます。ぜひ、本サイトのシミュレーターで様々な文字列の連結を試してみてください。