チューリングマシンによるテープ上の特定シンボル一括変換：シミュレーターで追う動作例
チューリングマシンは計算の基本的なモデルであり、その動作を理解することは計算機科学を学ぶ上で非常に重要です。本記事では、チューリングマシンを用いてテープ上の特定のシンボル全てを別のシンボルに変換するタスクを取り上げ、そのアルゴリズム設計とシミュレーター上での具体的な動作を解説します。
はじめに：チューリングマシンとテープ操作
チューリングマシンは、無限に長いテープ、テープ上の記号を読み書きするヘッド、そして現在の状態を保持する制御部から構成されます。計算は、現在の状態とヘッドが読み取った記号に基づき、あらかじめ定められた規則（遷移関数）に従って、テープに記号を書き込み、ヘッドを左右に移動させ、次の状態へ遷移するという一連の動作によって行われます。
基本的なテープ操作の一つに、テープ上のデータを走査し、条件に応じてデータを書き換える処理があります。特定シンボルの一括変換は、この書き換え処理の典型的な例です。例えば、「テープ上の全ての0を1に変換する」というタスクは、単純ながらもテープを端から端まで走査し、特定の記号を見つけたら書き換えるという、多くのアルゴリズムの基礎となる操作を含んでいます。
本記事では、この「特定シンボルの一括変換」タスクをチューリングマシンで実現する手順を解説し、シミュレーター上でその動作を追うことで、抽象的な遷移関数がどのように具体的なテープの変化をもたらすかを理解することを目的とします。
特定シンボル一括変換タスクの定義
ここでは、例として「テープ上の全てのaという記号をbという記号に変換する」というタスクを考えます。入力テープには、変換対象の記号（a）や他の記号が含まれているとします。テープの空白記号（□などで表されることが多い）は変換の対象外とします。
例：
- 入力テープ:
□ □ a a c a b □ □ - 期待される出力テープ:
□ □ b b c b b □ □
このタスクをチューリングマシンで実現するためには、以下の動作が必要です。
- テープの始端（あるいは入力文字列の始端）から走査を開始する。
- ヘッドを右方向へ移動させながら、テープ上の記号を一つずつ読み取る。
- 読み取った記号が
aであれば、そのマスにbを書き込む。 - 読み取った記号が
a以外の記号（bやcなど）であれば、何も書き換えずにそのままにする。 - テープ上の入力文字列の終端を示す空白記号（
□）に到達するまで、2〜4の動作を繰り返す。 - 終端の空白記号を読んだら、計算を停止する。
チューリングマシンの設計（遷移関数）
上記のタスクを実現するためのチューリングマシンの状態と遷移関数を設計します。最小限必要な状態を考えましょう。
- 状態 q0 (初期状態/走査状態): テープを右方向に走査しながら、
aを探し、見つけたらbに変換する状態。 - 状態 q1 (停止状態): 計算を終了する状態。
テープ記号は、変換対象のa、変換後のb、その他の記号（例:c）、そして空白記号□を考えます。
遷移関数 δ(現在の状態, 読み取った記号) = (書き込む記号, ヘッドの移動方向, 次の状態)
遷移規則は以下のようになります。
- δ(q0, a) = (b, R, q0)
- 状態q0で
aを読んだら、bと書き換え、ヘッドを右（R）に移動し、状態はq0のまま続ける。
- 状態q0で
- δ(q0, b) = (b, R, q0)
- 状態q0で
bを読んだら、bのまま（書き換えなし）、ヘッドを右に移動し、状態はq0のまま続ける。
- 状態q0で
- δ(q0, c) = (c, R, q0)
- 状態q0で
cを読んだら、cのまま、ヘッドを右に移動し、状態はq0のまま続ける。
- 状態q0で
- δ(q0, □) = (□, N, q1)
- 状態q0で空白記号
□を読んだら（これは入力文字列の終端に到達したことを意味します）、空白記号のまま、ヘッドを移動せず（N）、状態をq1（停止状態）に遷移する。
- 状態q0で空白記号
この遷移関数により、マシンはテープの左端から右端へ一度だけ走査し、全てのaをbに変換した後に停止します。
シミュレーターでの動作追跡
設計したチューリングマシンが、どのように動作するかをシミュレーターで確認してみましょう。入力テープを□ □ a a c a b □ □として、初期状態をq0、初期のヘッド位置を入力文字列の最初の記号（ここでは最初のaがあると仮定）に合わせます。
| ステップ | 現在の状態 | 読み取った記号 | 書き込む記号 | ヘッド移動 | 次の状態 | テープの状態 (ヘッド位置を示す ^) | 適用した遷移規則 |
| :------- | :--------- | :------------- | :----------- | :------- | :------- | :----------------------------- | :--------------- |
| 0 | q0 | a | b | R | q0 | □ □ a a c a b □ □
^ | δ(q0, a) |
| 1 | q0 | a | b | R | q0 | □ □ b a c a b □ □
^ | δ(q0, a) |
| 2 | q0 | c | c | R | q0 | □ □ b b c a b □ □
^ | δ(q0, c) |
| 3 | q0 | a | b | R | q0 | □ □ b b c a b □ □
^ | δ(q0, a) |
| 4 | q0 | b | b | R | q0 | □ □ b b c b b □ □
^ | δ(q0, b) |
| 5 | q0 | □ | □ | N | q1 | □ □ b b c b b □ □
^ | δ(q0, □) |
| 6 | q1 | (停止) | - | - | - | □ □ b b c b b □ □
^ | 停止 |
シミュレーター上でこの遷移関数を設定し、入力aaca b（前後の空白記号はシミュレーターが自動的に扱う場合が多い）を与えて実行すると、上記のようなステップでテープの状態が変化していく様子を確認できます。
シミュレーターの画面上では、
* 「現在の状態」は、通常、q0, q1といったラベルで表示されます。
* 「テープの状態」は、テープの内容とヘッドの位置（カーソルやマーカーなどで示されます）で視覚的に表示されます。
* 「読み取った記号」「書き込む記号」「ヘッドの移動方向」「次の状態」は、各ステップの実行時に表示される情報や、遷移関数テーブルの形で確認できます。
これらの表示を追いながら、どの遷移規則が適用され、テープがどのように変化しているかを観察することで、チューリングマシンの計算プロセスをより深く理解することができるでしょう。
まとめ
本記事では、チューリングマシンを用いたテープ上の特定シンボル一括変換タスクを取り上げ、その実現のための遷移関数の設計と、シミュレーター上での動作追跡について解説しました。
単純な「aをbに変換する」というタスクであっても、チューリングマシンでは現在の状態と読み取った記号に基づいて、次に取るべき行動（書き込み、移動、状態遷移）が厳密に定義されていることが分かりました。そして、このシンプルな規則の繰り返しによって、テープ全体にわたる変換処理が実現される様子を具体的なステップで追うことができました。
このような基本的なテープ操作の理解は、より複雑なアルゴリズムをチューリングマシンで表現する上での土台となります。ぜひ、お手持ちのシミュレーターで今回設計したチューリングマシンを実装し、様々な入力テープでその動作を確認してみてください。また、異なるシンボルへの変換や、複数のシンボルを同時に変換するタスクなどにも挑戦してみることをお勧めします。シミュレーションを通じて、計算の理論がどのように具体的な動作として現れるのかを体感していただければ幸いです。