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

チューリングマシンによるテープ上の特定シンボルの計数：シミュレーターで追う実現ステップ

チューリングマシンは、計算の概念を形式的に定義するために考案された仮想的な機械であり、現代のコンピュータの理論的な基礎となっています。その単純な構成要素にもかかわらず、チューリングマシンは原理的にあらゆる計算可能なタスクを実行できます。本記事では、チューリングマシンの基本的な応用例として、テープ上に書かれた特定種類の記号の数を数えるタスクを取り上げ、その実現方法を具体的な動作ステップとともに解説します。シミュレーターでの動作と理論的なステップの対応を理解することで、チューリングマシンの動作原理への理解を深めることを目指します。

特定シンボル計数タスクの定義

ここでは、チューリングマシンのテープ上に文字列が書かれていると仮定します。この文字列には複数の種類の記号が含まれている可能性があります。私たちのタスクは、その中の特定の記号（例: '1'）がテープ上にいくつ存在するかを数え、その結果をチューリングマシンの停止状態とともに出力することです。計数の結果は、例えばテープ上の特定の領域に別の記号（例: カウンター記号 'X'）を必要な数だけ書き込むことで表現することを考えます。

例: 入力テープ: 01101B (Bは空白記号) 数えたい記号: '1' 期待される結果: テープ上のどこかに3つのカウンター記号（例: XXX）が書き込まれている状態で停止。

計数アルゴリズムの概要

チューリングマシンが特定シンボルを計数するための基本的な戦略は以下のようになります。

1. テープを最初から最後まで一度走査し、数えたい記号を見つける。
2. 見つけた記号に「既に数えた」ことを示すマーク（別の記号）を付ける。
3. カウンター領域にヘッドを移動し、カウンター記号を一つ追加する。
4. テープの元の位置に戻り、まだ数えていない記号があるか確認するため、再度テープを走査する。
5. 全ての数えたい記号にマークが付くまで、このプロセスを繰り返す。
6. 全ての記号を数え終えたら、停止状態へ移行する。

このアルゴリズムを実現するために、チューリングマシンは複数の「状態」を持ち、それぞれがアルゴリズムの特定のステップを担当します。

チューリングマシンの構成要素と状態設計

このタスクを実行するチューリングマシンを設計するために、以下の要素を定義します。

• テープアルファベット: {'0', '1', 'B', 'x', 'X'} （入力記号: '0', '1', 空白: 'B', 数えたい記号'1'のマーク: 'x', カウンター記号: 'X'）
• 入力アルファベット: {'0', '1'}
• 状態:
  • q_init: 初期状態。テープを走査開始。
  • q_scan_right: 右方向へテープを走査し、数えたい記号'1'を探す状態。
  • q_mark_one: '1'を見つけた際に、それを'x'に書き換えて、カウンター領域へ移動開始する状態。
  • q_find_counter_area: カウンター領域（ここではテープの左端より前の領域と仮定）へ移動する状態。
  • q_increment_counter: カウンター記号'X'を書き込む状態。
  • q_return_to_scan: カウンター領域からテープの元の入力領域に戻る状態。
  • q_scan_left_for_x: テープの左端に戻るために左方向へ走査する状態。
  • q_check_more_ones: 全ての'1'を数え終えたか確認するため、右方向へ走査する状態。
  • q_finish: 全ての'1'を数え終え、停止準備をする状態。
  • q_halt: 停止状態。

遷移関数による動作ステップ解説

以下に、上記の状態とアルファベットに基づいた遷移関数（δ(現在の状態, 読み取った記号) = (書き込む記号, ヘッドの移動方向, 次の状態)）の例と、それに沿ったシミュレーターでの動作ステップを解説します。

1. 初期状態 q_init から開始:

   • チューリングマシンは q_init 状態から始まります。ヘッドはテープの左端（最初の記号）にあります。
   • 入力記号（'0', '1'）または空白'B'を読み取った場合、単に右へ移動し、q_scan_right 状態へ移行します。これはテープの入力領域を探索するためです。
     • δ(q_init, '0') = ('0', 右, q_scan_right)
     • δ(q_init, '1') = ('1', 右, q_scan_right)
     • δ(q_init, 'B') = ('B', 右, q_scan_right)

2. 右方向走査 q_scan_right:

   • この状態では、テープを右へ走査し、数えたい記号'1'を探します。
   • '0' や 'x'（既に数えたマーク）を見つけた場合は、そのまま右へ進みます。
     • δ(q_scan_right, '0') = ('0', 右, q_scan_right)
     • δ(q_scan_right, 'x') = ('x', 右, q_scan_right)
   • 数えたい記号'1'を見つけたら、次のステップ（マーク付けとカウンター移動）に進むため、q_mark_one 状態へ移行します。
     • δ(q_scan_right, '1') = ('x', 左, q_mark_one) // '1'を'x'に書き換え、左へ移動開始
   • テープの終端（最初の空白'B'）に達し、まだ'1'が見つかっていなければ、全ての'1'を数え終えた可能性があります。その場合は、確認のためにテープの左端に戻ります。
     • δ(q_scan_right, 'B') = ('B', 左, q_scan_left_for_x) // 全て数え終えたか確認へ

3. 記号のマーク付けとカウンター領域への移動 q_mark_one -> q_find_counter_area:

   • q_mark_one 状態では、直前に'x'と書き換えた位置から左へ移動を開始します。これはカウンター領域が左端にあると仮定しているためです。
   • δ(q_mark_one, '0') = ('0', 左, q_mark_one)
   • δ(q_mark_one, 'x') = ('x', 左, q_mark_one)
   • δ(q_mark_one, 'B') = ('B', 左, q_find_counter_area) // テープ左端の空白まで戻ったら、カウンター領域へ

4. カウンター記号の書き込み q_find_counter_area -> q_increment_counter:

   • q_find_counter_area 状態では、テープの左端の空白'B'に達しました。ここで左へ一歩移動し、カウンター領域に入ります。
   • δ(q_find_counter_area, 'B') = ('B', 左, q_increment_counter)
   • q_increment_counter 状態では、カウンター記号'X'を書き込み、すぐに右へ戻ります。これはカウンター領域をそれ以上侵さないためです。
   • δ(q_increment_counter, 'B') = ('X', 右, q_return_to_scan) // 'X'を書き込み、元の入力領域へ戻る

5. 元の入力領域への復帰 q_return_to_scan:

   • カウンター記号'X'を書き込んだ後、テープの入力領域に戻るため右へ移動します。
   • δ(q_return_to_scan, 'X') = ('X', 右, q_return_to_scan) // カウンター領域を通過
   • テープ左端の空白'B'に達したら、入力領域に入ったことになります。ここから再度'1'を探す走査を始めるために右へ移動し、q_scan_right 状態に戻ります。
   • δ(q_return_to_scan, 'B') = ('B', 右, q_scan_right)

6. 全数カウント完了の確認 q_scan_left_for_x -> q_check_more_ones -> q_finish:

   • q_scan_right 状態でテープ終端の空白'B'に達した場合、q_scan_left_for_x 状態へ移行し、テープ左端の空白まで戻ります。これは、数え残した'1'がないか確認するためです。
   • δ(q_scan_left_for_x, '0') = ('0', 左, q_scan_left_for_x)
   • δ(q_scan_left_for_x, 'x') = ('x', 左, q_scan_left_for_x)
   • δ(q_scan_left_for_x, 'B') = ('B', 右, q_check_more_ones) // 左端まで戻ったら確認走査へ
   • q_check_more_ones 状態では、右へ走査し、まだ'x'に置き換えられていない'1'が残っているか確認します。
   • 'x' または '0' を見つけたら、そのまま右へ進みます。
     • δ(q_check_more_ones, 'x') = ('x', 右, q_check_more_ones)
     • δ(q_check_more_ones, '0') = ('0', 右, q_check_more_ones)
   • もし'1'が残っていたら、まだ数え終えていないので、再びその'1'をマークしに行くために q_mark_one 状態へ移行します（この遷移は厳密には q_scan_right に書くべきですが、確認ステップからの戻りとして説明）。
     • δ(q_check_more_ones, '1') = ('x', 左, q_mark_one) // '1'を見つけたら、マークして数え直しサイクルへ
   • テープ終端の空白'B'に達し、その過程で'1'を見つけなかった（つまり全て'x'になっている）場合、全ての'1'を数え終えたと判断し、q_finish 状態へ移行します。
     • δ(q_check_more_ones, 'B') = ('B', 右, q_finish)

7. 終了処理 q_finish -> q_halt:

   • q_finish 状態では、計算が完了したことを示します。必要であれば、カウンター領域へヘッドを移動させて停止します。ここでは、単純に停止状態へ移行するとします。
   • δ(q_finish, 'B') = ('B', 右, q_halt) // 停止状態へ

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

上記の遷移関数を持つチューリングマシンをシミュレーターで実行すると、以下のような動作が観察できます。

• 状態遷移図: 各状態（q_init, q_scan_right, q_mark_one など）がノードとして表示され、矢印が遷移規則（例: '1'/x,L）を示します。シミュレーター実行中は、現在の状態に対応するノードがハイライトされます。
• テープの状態変化: シミュレーターのテープ表示上で、ヘッドが移動するたびに記号が読み取られ、必要に応じて書き換えられる様子が視覚的に確認できます。特に'1'が'x'に変わる瞬間や、テープ左端より前の領域に'X'が書き込まれる様子は、アルゴリズムの核心部分を捉えています。
• ヘッドの動き: ヘッドがテープ上を左右に移動する様子がリアルタイムで表示されます。右への走査、左端への移動、カウンター領域への出入りなどが直感的に理解できます。
• 現在の状態と次の動作: シミュレーターのコントロールパネルなどには、現在の状態、ヘッドが読み取っている記号、そして次に適用される遷移規則が表示されることが一般的です。これにより、「この記号を読み取ったから、この状態になり、ヘッドがこう動く」という論理的な繋がりをステップごとに追うことができます。

例えば、入力テープが 0110B で数えたい記号が '1' の場合、シミュレーターでは以下のような一連のステップが再現されます（遷移は一部省略、理想的な動き）。

1. q_init で開始。右へ移動して q_scan_right へ。テープは 0110B。
2. q_scan_right で '0' を読み取り、右へ移動。テープは 0110B。
3. q_scan_right で '1' を読み取り。これを 'x' に書き換え、左へ移動。テープは 0x10B。状態は q_mark_one へ。
4. q_mark_one で '0' を読み取り、左へ移動。テープは 0x10B。
5. q_mark_one で 'x' を読み取り、左へ移動。テープは 0x10B。
6. q_mark_one で左端の 'B' を読み取り、左へ移動。テープは B0x10B。状態は q_find_counter_area へ。
7. q_find_counter_area で左の 'B' を読み取り、左へ移動。テープは BB0x10B。状態は q_increment_counter へ。
8. q_increment_counter で 'B' に 'X' を書き込み、右へ移動。テープは X B 0x10B。状態は q_return_to_scan へ。
9. q_return_to_scan で 'B' を読み取り、右へ移動。テープは X B 0x10B。状態は q_scan_right へ。
10. q_scan_right で '0', 'x' を読み取り、右へ移動。
11. q_scan_right で次の '1' を読み取り。これを 'x' に書き換え、左へ移動。テープは X B 0xx0B。状態は q_mark_one へ。
12. ...（同様のサイクルを繰り返し、カウンター領域に二つ目の'X'を書き込む）...
13. カウンター領域に二つ目の'X'が書かれ、テープは XX B 0xx0B となった後、再び q_scan_right へ。
14. q_scan_right で '0', 'x', 'x', '0' を読み取り、右へ移動。
15. q_scan_right で終端の 'B' を読み取り。今回は新しい'1'が見つからなかったので、左端に戻る確認サイクルへ。状態は q_scan_left_for_x へ。
16. q_scan_left_for_x で左へ移動し、テープ左端の 'B' に戻る。テープは XX B 0xx0B。状態は q_check_more_ones へ。
17. q_check_more_ones で右へ走査。'0', 'x', 'x', '0', 'B' を順に読み取るが、'1'は見つからない。
18. q_check_more_ones で終端の 'B' を読み取り、全ての'1'が'x'になっていることを確認。状態は q_finish へ。
19. q_finish で 'B' を読み取り、右へ移動。状態は q_halt へ。
20. q_halt 状態で停止。テープの左端には XX とカウンター記号が二つ書かれている（入力例 0110B では'1'は二つ）。

シミュレーター上では、これらのステップが視覚的に再現されるため、抽象的な遷移規則が具体的なテープ操作やヘッドの動きにどう繋がるかを容易に理解できます。

まとめ

本記事では、チューリングマシンを使ってテープ上の特定の記号を計数するタスクの実現方法を解説しました。このタスクは、チューリングマシンの基本的な操作である「記号の読み書き」「ヘッドの移動」「状態遷移」を組み合わせることで実行可能であることを示しています。

特に、数えたい記号を別の記号でマークしながら、テープの別の領域をカウンターとして使用するというアプローチは、限られたリソース（テープ、ヘッド位置、状態）の中で複雑な情報を管理するチューリングマシンの工夫の一端を示しています。

シミュレーターを活用することで、ここで解説した状態遷移やテープの状態変化、ヘッドの動きを実際に追体験できます。これにより、チューリングマシンの理論的なモデルが、どのように具体的なアルゴリズムとして実装され、動作するのかをより深く理解することができるでしょう。ぜひ、様々な入力パターンを試したり、カウンターの表現方法を変えてみたりするなど、シミュレーターでの実験を通じてチューリングマシンの世界を探求してみてください。