チューリングマシンによる特定記号の削除:シミュレーターで追う動作ステップ
はじめに
チューリングマシンは、計算の究極的なモデルとして計算機科学の基礎をなしています。その基本的な動作は、テープ上の記号を読み取り、書き換え、ヘッドを移動させ、状態を遷移させることですが、これらの単純な操作の組み合わせによって、驚くほど多様な計算を実現できます。
本記事では、チューリングマシンがテープ上に書かれた特定の記号をすべて削除し、削除によって生じた空白を詰める(後続の記号を左にシフトする)操作をどのように行うか、その具体的な動作ステップを解説します。この操作は、文字列処理における基本的な操作の一つであり、チューリングマシンのテープ操作能力を理解する上で良い例となります。シミュレーター上でこのアルゴリズムを実行することで、理論上の状態遷移やテープ変化がどのように具体化されるのかを視覚的に確認することができます。
特定記号削除の課題
テープ上から特定の記号(ここでは例として'x'とします)を削除するだけなら簡単そうに思えますが、単に'x'を空白記号(ここでは'B'とします)に書き換えるだけでは、'x'があった場所に空白が残ってしまいます。
例:axbycxd
というテープ内容から 'x' を削除する場合
単純な書き換え:a B y B c B d
(Bは空白記号)
求められる結果は、削除された記号によってできた隙間が詰められた状態、つまり abycd
となることです。そのためには、'x'を削除した後に、その右側にある記号を一つずつ左にシフトさせる操作が必要になります。
アルゴリズムの概要
特定記号('x')を削除し、空白を詰めるアルゴリズムは、以下のような流れで実現できます。
- テープの左端から開始し、特定の記号('x')を探します。
- 'x'を見つけたら、その'x'を一時的にマークするか、あるいはすぐに後続の記号を左にシフトする準備をします。
- 'x'を見つけた位置から右方向へ移動し、次の非空白記号を探します。
- 見つけた非空白記号を、'x'が見つかった位置にコピーします。
- コピー元の非空白記号があった位置を空白記号で上書きします。
- テープ全体を右端まで見て、左シフトが必要な記号がなくなるまで、ステップ3-5を繰り返します。
- テープの右端までシフトが完了したら、元の'x'があった位置(またはコピー先の位置)の右隣から再び'x'を探す操作に戻ります。
- テープの右端まで走査しても'x'が見つからなければ処理を終了します。
この処理を実現するために、チューリングマシンは複数の状態を持つ必要があります。
状態設計
このアルゴリズムを実現するためのチューリングマシンの状態遷移の例を考えます。使用するアルファベットは、入力記号(a, b, c, d, yなど)、削除対象記号(x)、空白記号(B)、そして処理中に使用する一時的なマーク記号(例:右端を示す'#'など)とします。
-
Find_X
状態: テープの左から右へ移動しながら、削除対象の記号 'x' またはテープの終端を示す記号 '#' を探します。- 'x'以外の入力記号を読んだ場合:記号はそのまま、右へ移動し、状態は
Find_X
のまま。 - 'x'を読んだ場合:この 'x' を削除するため、状態を
Shift_Start
に遷移させます。ヘッドは右へ移動し、シフトする記号を探し始めます。 - テープ終端 '#' を読んだ場合:全ての 'x' の処理が完了したと判断し、終了状態
Halt
に遷移します。
- 'x'以外の入力記号を読んだ場合:記号はそのまま、右へ移動し、状態は
-
Shift_Start
状態: 'x' を見つけた直後の状態です。削除対象の位置の右側から、左にシフトすべき最初の記号を探し始めます。ヘッドは右へ移動します。- 非空白記号を読んだ場合:この記号を左にシフトする必要があります。状態を
Shifting
に遷移させます。ヘッドは右へ移動し、シフト元の位置を記憶しておきます(これは状態遷移図では直接表現できませんが、多テープチューリングマシンや、状態に情報をエンコードすることで実現できます。ここでは概念的な説明とします)。シングルテープマシンでは、シフト元の位置に戻るために右端まで行ってから左に戻るなどの複雑な動きが必要になります。簡潔のため、ここではシフト操作を抽象的に扱います。 - 空白記号 'B' または終端 '#' を読んだ場合:これ以上シフトすべき記号がないことを意味します。削除対象の 'x' を空白に書き換え、左に戻って次の 'x' を探す状態
Rewind_for_Next_X
に遷移します。
- 非空白記号を読んだ場合:この記号を左にシフトする必要があります。状態を
-
Shifting
状態: 左シフト処理を実行中の状態です。具体的な実装は複雑になりますが、概念的には、右側にある記号を一つ左の空白位置に移動させ、移動元の位置を空白にする操作を繰り返します。- シフトすべき次の非空白記号を見つけたら、それをコピー元として処理します。
- 全ての記号を左にシフトし終えたら、
Shift_Start
で見つけた 'x' の位置に戻るか、あるいは左端まで戻ってから再びFind_X
状態に入ります。シングルテープでは後者のアプローチが一般的です。
-
Rewind_for_Next_X
状態: 一連のシフト処理が完了した後、テープの左端に戻り、次の 'x' 探しを再開するための状態です。ヘッドを左へ移動させ続けます。- テープの左端に到達したことを示す記号(またはテープの端そのもの)を検出したら、状態を
Find_X
に戻します。 - 左端到達前に非空白記号や空白記号を読んだ場合:記号はそのまま、左へ移動し、状態は
Rewind_for_Next_X
のまま。
- テープの左端に到達したことを示す記号(またはテープの端そのもの)を検出したら、状態を
-
Halt
状態: 処理が終了した状態です。
シミュレーターでの動作ステップ例
例として、テープ内容が axbycxd#
(#は終端記号)の場合に、記号 'x' を削除するシミュレーターでの動作を追ってみましょう。初期状態は Find_X
、ヘッドは一番左の 'a' の位置にあるとします。
-
状態:
Find_X
- ヘッド位置 1: 'a' を読む -> 'a' のまま, 右移動, 状態
Find_X
- ヘッド位置 2: 'x' を読む -> 状態
Shift_Start
へ遷移, 右移動 - テープ:
axbycxd#
->axbycxd#
- ヘッド: a->x
- ヘッド位置 1: 'a' を読む -> 'a' のまま, 右移動, 状態
-
状態:
Shift_Start
(最初の 'x' の右隣から開始)- ヘッド位置 3: 'b' を読む -> 状態
Shifting
へ遷移, 右移動
- ヘッド位置 3: 'b' を読む -> 状態
-
状態:
Shifting
(シフト処理 - この部分はシミュレーターでの詳細な状態遷移として表現されます)- ヘッド位置 4: 'y' を読む -> この 'y' を左('x' があった位置)にコピーする準備。
- ...複雑な状態遷移を経て、'y' を 'x' の位置(位置2)に書き込み、元の 'y' の位置(位置4)を空白にする。
- テープ:
axbycxd#
->ayBycxd#
(yを左にシフト) -
ヘッドはさらに右へ移動し、次の記号を探す。
-
ヘッド位置 5: 'c' を読む -> この 'c' を左('y' が書き込まれた位置の右隣、つまり元の 'b' の位置3)にコピーする準備。
- ...同様に 'c' を位置3に書き込み、元の 'c' の位置(位置5)を空白にする。
-
テープ:
ayBycxd#
->aycByxd#
(cを左にシフト) -
ヘッド位置 6: 'x' を読む -> 削除対象の 'x' ですが、ここではシフト元の記号として扱います。この 'x' を左('c' が書き込まれた位置の右隣、つまり元の 'B' の位置4)にコピーする準備。
- ... 'x' を位置4に書き込み、元の 'x' の位置(位置6)を空白にする。
-
テープ:
aycByxd#
->aycxB d#
(xを左にシフト) -
ヘッド位置 7: 'd' を読む -> この 'd' を左('x' が書き込まれた位置の右隣、つまり元の 'B' の位置5)にコピーする準備。
- ... 'd' を位置5に書き込み、元の 'd' の位置(位置7)を空白にする。
-
テープ:
aycxB d#
->aycxdB #
(dを左にシフト) -
ヘッド位置 8: '#' を読む -> テープの終端に到達しました。これ以上シフトすべき記号はありません。
- ここで、最初に削除対象として見つけた 'x' の位置(位置2)を空白 'B' で上書きする必要があります。これは
Shifting
状態の最終ステップで行うか、Shift_Start
状態からの遷移で実現できます。ここでは位置2が 'y' で上書きされているため、最後に余分な空白ができてしまいます。これを避けるためには、'x' を見つけた位置に、右からシフトしてきた記号を直接書き込むように状態設計を工夫する必要があります。
より洗練されたアプローチとしては、以下のようになります。 1.
Find_X
で 'x' (位置2) を見つける。 2. 状態Shift_Mode
へ遷移し、ヘッドを右に進める (位置3)。 3.Shift_Mode
で非空白記号 'b' (位置3) を見つける。これを 'x' があった位置2に書き込む。テープはabyycxd#
となる。ヘッドは元の 'b' の位置3に戻る。 4. 位置3を空白 'B' で上書きする。テープはaByycxd#
となる。ヘッドは右へ移動 (位置4)。 5. 位置4の 'y' を見つける。これを一つ左、つまり位置3に書き込む。テープはabyBcxd#
となる。ヘッドは元の 'y' の位置4に戻る。 6. 位置4を空白 'B' で上書きする。テープはabBBcxd#
となる。ヘッドは右へ移動 (位置5)。 7. ...この操作を '#' に到達するまで繰り返します。 8. 最終的にテープはabycdBBB#
のようになります。後続の空白記号はチューリングマシンによっては無視されるか、別の後処理状態ですべて削除される場合がありますが、ここではabycd
部分が正しく生成されたと見なします。シミュレーターでこの動作を追う際は、各ステップでテープの内容がどのように変化し、ヘッドがどこに移動し、状態がどのように遷移するかを注意深く観察してください。特に、記号を「移動」させるために、一度読み取った記号を別の場所に書き込み、元の場所を空白にするという手順を確認できます。
-
状態:
Rewind_for_Next_X
(シフト処理後、次の 'x' を探すために左に戻る)- ヘッドが右端(またはシフト操作の最終位置)から左へ移動し始めます。
- ヘッド位置... 左移動... 左移動...
- ヘッド位置 1: 左端('a' の左隣、または特別な左端記号)に到達。
- 状態
Find_X
へ遷移。ヘッドは右移動(位置1の 'a' へ)。
-
状態:
Find_X
(左端に戻って再度 'x' を探す)- ヘッド位置 1: 'a' を読む -> 'a' のまま, 右移動, 状態
Find_X
- ヘッド位置 2: 'y' を読む (テープは既に
abycdBBB#
のようになっている) -> 'y' のまま, 右移動, 状態Find_X
- ヘッド位置 3: 'c' を読む -> 'c' のまま, 右移動, 状態
Find_X
- ヘッド位置 4: 'd' を読む -> 'd' のまま, 右移動, 状態
Find_X
- ヘッド位置 5: 'B' を読む -> 'B' のまま, 右移動, 状態
Find_X
- ...空白記号を読みながら右へ移動...
- ヘッド位置 ...: '#' を読む -> テープ終端に到達。
- 状態
Halt
へ遷移。
- ヘッド位置 1: 'a' を読む -> 'a' のまま, 右移動, 状態
-
状態:
Halt
(処理終了)- シミュレーターの実行が停止します。最終的なテープ内容は
abycdBBB#
のようになっているはずです。
- シミュレーターの実行が停止します。最終的なテープ内容は
シミュレーターとの対応
シミュレーター上では、以下の要素が理論上の概念と対応します。
- テープ表示: チューリングマシンのテープ上の現在の記号列を示します。各ステップで記号が書き換えられる様子や、空白記号が増減する様子を確認できます。
- ヘッド位置: ヘッドがテープ上のどのセルを読んでいるかを示します。ヘッドが左や右に移動する様子を追うことで、テープ走査のパターンを理解できます。
- 現在の状態表示: チューリングマシンが現在どの状態にあるか(例:
Find_X
,Shift_Start
,Shifting
,Rewind_for_Next_X
など)を示します。アルゴリズムのどの段階にいるかを把握するのに役立ちます。 - 遷移表/状態遷移図: 各状態と読み取った記号の組み合わせに対して、次にどの状態へ遷移し、どの記号を書き込み、ヘッドをどちらへ移動させるかという遷移関数の内容を示します。シミュレーターはまさにこの遷移関数に従って動作します。
特定記号の削除という比較的単純な操作であっても、シングルテープチューリングマシンで効率的に実装しようとすると、複雑な状態遷移とテープ操作が必要になることが分かります。シミュレーターを用いて上記のステップを追体験することで、この複雑さがどのように実現されているのかを視覚的に理解し、チューリングマシンの計算能力とその限界の一端を感じ取ることができるでしょう。
結論
本記事では、チューリングマシンによる特定記号の削除と後続記号の左シフトという操作に焦点を当て、そのアルゴリズム概要、状態設計の考え方、そしてシミュレーター上での動作ステップ例を解説しました。単純な文字列操作も、チューリングマシンのモデル上で実現しようとすると、状態設計やテープ操作に工夫が必要となることがお分かりいただけたかと思います。
シミュレーターを活用する際は、単に実行結果を見るだけでなく、一歩ずつ実行を進めて、その都度「現在の状態」「ヘッド位置」「テープ内容」がどのように変化しているかを確認し、「どの遷移規則が適用されたか」を意識することが、チューリングマシンの動作原理を深く理解する鍵となります。ぜひ様々な入力テープで試してみてください。