チューリングマシンによるテープデータのコピー：シミュレーターで追う実現ステップ
はじめに
チューリングマシンは、計算の最も基本的なモデルとして計算機科学において重要な位置を占めています。これまでの記事では、チューリングマシンの基本的な構成要素や、簡単なパターン認識、加算といった例を通じてその動作原理を解説してまいりました。
本記事では、チューリングマシンが「テープ上のデータを別の場所にコピーする」という操作をどのように実現するのかを詳細に解説します。データのコピーは、より複雑なアルゴリズムを構築する上での基礎となる重要な操作です。シミュレーターを使ってこのデータコピーのプロセスをステップバイステップで追うことで、抽象的な状態遷移やテープ操作が具体的な計算にいかに結びつくかを深く理解することができます。
チューリングマシンにおけるデータコピーの課題
人間の視点では、テープ上の文字列を見て、それを別の場所に書き写すことは容易に思えます。しかし、チューリングマシンは単一のヘッドしか持たず、現在の状態と読み取った記号に基づいて機械的に動作します。一度に複数の記号を見たり、直前の記号を「覚えておく」能力は状態遷移に組み込まなければ実現できません。
特に、元のデータを破壊せずにコピーを作成する場合、単純に読みながら書き込むという操作はできません。元のデータを読み取った後、コピー先の位置までヘッドを移動させ、書き込み、そして再び元の場所に戻って次の記号を処理するという一連の手順を、状態遷移によって正確に制御する必要があります。このプロセスには、現在コピーしている記号が何か、テープ上のどこまでがコピー元でどこからがコピー先か、次に処理すべき記号はどれか、といった情報を状態やテープ上の特殊な記号（マーカー）で管理する工夫が必要となります。
データコピーを実現する基本的な戦略
テープ上の文字列 w を、その右側にコピーするシナリオを考えます。例えば、入力テープが BwBB... （Bはブランク記号）であった場合、最終的に Bw w B... のような状態を目指します。
一般的な戦略は以下のようになります。
- コピー元の記号を読み取る: ヘッドを左から右へ移動させながら、コピー元の未処理の記号を一つ読み取ります。読み取った記号を「記憶」するため、その記号に対応する特定の状態へ遷移します。また、その記号がすでに処理済みであることを示すために、テープ上の元の場所には特殊なマーカー記号を書き込むことが有効です。
- コピー先の末尾へ移動する: 読み取った記号を「記憶」した状態のまま、テープの右方向へ移動し、コピー先の現在の末尾（最初のコピーの場合は元の文字列の直後、以降はコピー済みの部分の直後）を探します。コピー先の末尾を示すためにも、特殊なマーカー記号を使用することがあります。
- 記号を書き込む: コピー先の末尾に到達したら、記憶していた記号をテープに書き込みます。
- コピー元へ戻る: 記号を書き込んだ後、再び左方向へヘッドを移動させ、次に処理すべきコピー元の記号を探します。これは、ステップ1で書き込んだマーカー記号を目印に行うことができます。
- 繰り返し: 次に処理すべきコピー元の記号を見つけたら、再びステップ1へ戻り、このプロセスを繰り返します。
- 終了: コピー元の全ての記号を処理済みとしてマークし終えたら、コピー操作は完了です。終了状態へ遷移します。
この戦略をチューリングマシンの状態遷移として具体的に定義します。
データコピー用チューリングマシンの設計例
簡単な例として、入力アルファベット {a, b} とブランク記号 {B} を使用し、文字列 ab をコピーするチューリングマシンを設計します。テープ上のマーカーとして、コピー元で処理済みの a は A に、処理済みの b は B' に、コピー先の末尾は # で示し（簡略化のため今回は使用しないか、状態のみで管理）、処理後に元の記号に戻すような設計も考えられますが、ここではシンプルに処理済みマーカーだけを使用します。最終的に元の記号に戻す処理は省略します。
アルファベット:
* 入力アルファベット: {a, b}
* テープアルファベット: {a, b, B, A, B'} (B はブランク、A は処理済み 'a' のマーカー、B' は処理済み 'b' のマーカー)
状態:
* q_start: 初期状態
* q_read_a: 'a' を読み取り、記憶している状態
* q_read_b: 'b' を読み取り、記憶している状態
* q_find_copy_end_a: 'a' を記憶し、コピー先の末尾を探している状態
* q_find_copy_end_b: 'b' を記憶し、コピー先の末尾を探している状態
* q_write_a: 'a' を書き込む状態
* q_write_b: 'b' を書き込む状態
* q_find_original: コピー元に戻るために左方向へ移動している状態
* q_return_to_start: コピー元の先頭近くに戻る状態
* q_halt: 終了状態
遷移関数 δ(現在の状態, 読み取った記号) = (次の状態, 書き込む記号, ヘッドの移動方向)
| 現在の状態 | 読み取った記号 | 次の状態 | 書き込む記号 | 移動方向 | 解説 |
| :------------------ | :------------- | :------------------ | :----------- | :------- | :----------------------------------------- |
| q_start | a | q_read_a | A | R | 'a' を読み取り、処理済みマーク A を書き込み、記憶 |
| q_start | b | q_read_b | B' | R | 'b' を読み取り、処理済みマーク B' を書き込み、記憶 |
| q_start | A | q_start | A | R | 処理済み 'a' はスキップ |
| q_start | B' | q_start | B' | R | 処理済み 'b' はスキップ |
| q_start | B | q_return_to_start | B | L | コピー元末尾に到達、終了処理へ |
| q_read_a | a, b, A, B' | q_find_copy_end_a | 記号を変えず | R | 'a' 記憶中に他の記号をスキップし右へ移動 |
| q_read_a | B | q_write_a | a | L | 'a' 記憶中にブランクに到達、'a' を書き込み左へ |
| q_read_b | a, b, A, B' | q_find_copy_end_b | 記号を変えず | R | 'b' 記憶中に他の記号をスキップし右へ移動 |
| q_read_b | B | q_write_b | b | L | 'b' 記憶中にブランクに到達、'b' を書き込み左へ |
| q_find_copy_end_a | a, b, A, B' | q_find_copy_end_a | 記号を変えず | R | コピー先末尾 (ブランク) を探し右へ移動 |
| q_find_copy_end_a | B | q_write_a | a | L | ブランクに到達、'a' を書き込み左へ |
| q_find_copy_end_b | a, b, A, B' | q_find_copy_end_b | 記号を変えず | R | コピー先末尾 (ブランク) を探し右へ移動 |
| q_find_copy_end_b | B | q_write_b | b | L | ブランクに到達、'b' を書き込み左へ |
| q_write_a | a, b, B, A, B' | q_find_original | 記号を変えず | L | 書き込み後、コピー元を探し左へ移動 |
| q_write_b | a, b, B, A, B' | q_find_original | 記号を変えず | L | 書き込み後、コピー元を探し左へ移動 |
| q_find_original | a, b, B' | q_find_original | 記号を変えず | L | 処理済みマーカー A を探し左へ移動 |
| q_find_original | A | q_start | A | R | 処理済みマーカー A を発見、次の未処理記号へ |
| q_return_to_start | A, B' | q_return_to_start | 記号を変えず | L | コピー元末尾から先頭 B を探し左へ移動 |
| q_return_to_start | B | q_halt | B | R | 先頭 B に到達、終了状態へ移行 |
シミュレーターでの動作ステップ解説 (入力 "ab")
それでは、入力テープが B a b B B B ... の状態で、このチューリングマシンがどのように動作するかをシミュレーターで追ってみましょう。シミュレーター上では、現在の状態、ヘッド位置、テープの内容が視覚的に確認できます。
- 初期状態:
q_start, テープ:B a b B B B ..., ヘッドは最初のaの位置。 - ステップ1:
q_startでaを読み取る ->δ(q_start, a) = (q_read_a, A, R)- 状態:
q_read_a - テープ:
B A b B B B ... - ヘッド:
bの位置へ移動 - 解説: 'a' を読み取り、それを記憶（状態
q_read_aに反映）。テープ上の 'a' を処理済みマーカーAに書き換え、右へ移動。
- 状態:
- ステップ2:
q_read_aでbを読み取る ->δ(q_read_a, b) = (q_find_copy_end_a, b, R)- 状態:
q_find_copy_end_a - テープ:
B A b B B B ... - ヘッド: 1つ目の
Bの位置へ移動 - 解説: 'a' を記憶したまま、コピー先の末尾を探すため右へ移動。読み取った 'b' は変更しない。
- 状態:
- ステップ3:
q_find_copy_end_aで 1つ目のBを読み取る ->δ(q_find_copy_end_a, B) = (q_write_a, a, L)- 状態:
q_write_a - テープ:
B A b a B B ... - ヘッド:
bの位置へ移動 - 解説: コピー先末尾のブランクを見つけ、記憶していた 'a' を書き込む。コピーが終わったので、元の場所へ戻るために左へ移動。
- 状態:
- ステップ4:
q_write_aでbを読み取る ->δ(q_write_a, b) = (q_find_original, b, L)- 状態:
q_find_original - テープ:
B A b a B B ... - ヘッド:
Aの位置へ移動 - 解説: コピー元を探す状態に遷移し、左へ移動。
- 状態:
- ステップ5:
q_find_originalでAを読み取る ->δ(q_find_original, A) = (q_start, A, R)- 状態:
q_start - テープ:
B A b a B B ... - ヘッド:
bの位置へ移動 - 解説: 処理済みマーカー
Aを見つけ、次の未処理記号があるはずの場所へ戻る。状態をq_startに戻し、次のコピー準備完了。
- 状態:
- ステップ6:
q_startでbを読み取る ->δ(q_start, b) = (q_read_b, B', R)- 状態:
q_read_b - テープ:
B A B' a B B ... - ヘッド:
aの位置へ移動 - 解説: 次の記号 'b' を読み取り、記憶（状態
q_read_b）。テープ上の 'b' を処理済みマーカーB'に書き換え、右へ移動。
- 状態:
- ステップ7:
q_read_bでaを読み取る ->δ(q_read_b, a) = (q_find_copy_end_b, a, R)- 状態:
q_find_copy_end_b - テープ:
B A B' a B B ... - ヘッド: 1つ目の
Bの位置へ移動 - 解説: 'b' を記憶したまま、コピー先の末尾を探すため右へ移動。読み取った 'a' は変更しない。
- 状態:
- ステップ8:
q_find_copy_end_bで 1つ目のBを読み取る ->δ(q_find_copy_end_b, B) = (q_write_b, b, L)- 状態:
q_write_b - テープ:
B A B' a b B ... - ヘッド:
aの位置へ移動 - 解説: コピー先末尾のブランクを見つけ、記憶していた 'b' を書き込む。コピーが終わったので、元の場所へ戻るために左へ移動。
- 状態:
- ステップ9:
q_write_bでaを読み取る ->δ(q_write_b, a) = (q_find_original, a, L)- 状態:
q_find_original - テープ:
B A B' a b B ... - ヘッド:
B'の位置へ移動 - 解説: コピー元を探す状態に遷移し、左へ移動。
- 状態:
- ステップ10:
q_find_originalでB'を読み取る ->δ(q_find_original, B') = (q_find_original, B', L)- 状態:
q_find_original - テープ:
B A B' a b B ... - ヘッド:
Aの位置へ移動 - 解説: 処理済みマーカー
B'を見つけたが、目的のAではないのでさらに左へ移動。
- 状態:
- ステップ11:
q_find_originalでAを読み取る ->δ(q_find_original, A) = (q_start, A, R)- 状態:
q_start - テープ:
B A B' a b B ... - ヘッド:
B'の位置へ移動 - 解説: 処理済みマーカー
Aを発見。その右（元の位置）に戻り、次の未処理記号を探す。状態をq_startに戻す。
- 状態:
- ステップ12:
q_startでB'を読み取る ->δ(q_start, B') = (q_start, B', R)- 状態:
q_start - テープ:
B A B' a b B ... - ヘッド:
aの位置へ移動 - 解説: 処理済みマーカー
B'を見つけ、スキップして右へ移動。
- 状態:
- ステップ13:
q_startでBを読み取る ->δ(q_start, B) = (q_return_to_start, B, L)- 状態:
q_return_to_start - テープ:
B A B' a b B ... - ヘッド:
bの位置へ移動 - 解説: コピー元の末尾のブランクに到達。全ての記号の処理が終わったと判断し、終了処理へ。元の先頭に戻るため左へ移動。
- 状態:
- ステップ14:
q_return_to_startでbを読み取る ->δ(q_return_to_start, b) = (q_return_to_start, b, L)- 状態:
q_return_to_start - テープ:
B A B' a b B ... - ヘッド:
aの位置へ移動 - 解説: 先頭のブランクを探して左へ移動。
- 状態:
- ステップ15:
q_return_to_startでaを読み取る ->δ(q_return_to_start, a) = (q_return_to_start, a, L)- 状態:
q_return_to_start - テープ:
B A B' a b B ... - ヘッド:
B'の位置へ移動 - 解説: 先頭のブランクを探して左へ移動。
- 状態:
- ステップ16:
q_return_to_startでB'を読み取る ->δ(q_return_to_start, B') = (q_return_to_start, B', L)- 状態:
q_return_to_start - テープ:
B A B' a b B ... - ヘッド:
Aの位置へ移動 - 解説: 先頭のブランクを探して左へ移動。
- 状態:
- ステップ17:
q_return_to_startでAを読み取る ->δ(q_return_to_start, A) = (q_return_to_start, A, L)- 状態:
q_return_to_start - テープ:
B A B' a b B ... - ヘッド: 最初の
Bの位置へ移動 - 解説: 先頭のブランクを探して左へ移動。
- 状態:
- ステップ18:
q_return_to_startで最初のBを読み取る ->δ(q_return_to_start, B) = (q_halt, B, R)- 状態:
q_halt - テープ:
B A B' a b B ... - ヘッド:
Aの位置へ移動 - 解説: 先頭のブランクに到達。全ての処理が完了したため、終了状態へ移行。計算が停止します。
- 状態:
最終的なテープの状態は B A B' a b B ... となり、元の文字列 "ab" のコピー "ab" がテープ上に生成されました（元の位置はマーカーに変わっていますが、元の記号に戻す処理を追加すれば、最終的に B a b a b B ... とすることも可能です）。
シミュレーターでこのステップを一つずつ実行することで、各状態がどのような役割を持ち、ヘッドの動きやテープの内容がどのように変化していくかを視覚的に確認できます。特に、記号を「記憶」するために状態を使用している点や、元の位置に戻るために処理済みマーカーをたどっている点など、チューリングマシンならではの工夫が理解できるでしょう。
まとめ
本記事では、チューリングマシンによるテープ上のデータコピーの実装例を解説しました。単一のヘッドと単純な状態遷移という制約の中でデータコピーを実現するためには、状態を活用した情報の記憶や、テープ上のマーカーによる位置管理といった工夫が必要であることを示しました。
今回示したデータコピーの例は、チューリングマシンが単なるパターン認識や単純な算術演算だけでなく、データの構造を操作する能力を持つことを示しています。このような基本的な操作を組み合わせることで、チューリングマシンは理論上、どのような計算も実行できる万能性を持つことになります。
ぜひご自身でチューリングマシンシミュレーターを操作し、この記事で解説したデータコピーの動作を再現してみてください。各ステップで状態、ヘッド、テープの内容がどのように連動して変化するかを観察することで、チューリングマシンの動作原理と計算のメカニズムに対する理解がさらに深まるはずです。
チューリングマシンの学習は、計算の限界や可能性を理解する上で非常に価値があります。今後も様々な計算タスクをチューリングマシンでどのように表現できるかを学び、計算機科学の基礎理論への理解を深めていきましょう。