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

チューリングマシンによる単項表現の乗算：シミュレーターで追う実装ステップ

はじめに

本稿では、チューリングマシンがどのようにして数値を計算できるのか、その一例として「単項表現による乗算」を取り上げ、シミュレーターでの動作を追いながら詳細に解説します。チューリングマシンは、その単純な構成要素にも関わらず、私たちが考えるあらゆる計算を実行できる計算可能性を持つ普遍的な計算モデルです。単項表現での乗算は、加算やコピーといった基本的な操作を組み合わせることで実現でき、チューリングマシンの動作原理を具体的に理解するのに非常に適しています。

計算機科学を学ぶ上で、抽象的な理論だけでなく、それがどのように具体的な「動作」として実現されるのかを把握することは重要です。シミュレーターを活用することで、チューリングマシンの状態遷移、テープ上のデータの変化、ヘッドの動きなどを視覚的に追跡でき、理論と実際の動作の繋がりを深く理解することができます。

単項表現と乗算の定義

まず、本稿で扱う「単項表現」と「乗算」について定義します。

単項表現 (Unary Representation)

単項表現は、数値を特定の単一の記号（例えば 0）を繰り返すことによって表現する方法です。数値 n は、記号 0 を n 個並べることで表されます。

例： * 数値 0 は 空（ε） または 特殊な記号で表現 * 数値 1 は 0 * 数値 2 は 00 * 数値 3 は 000

この表現方式は、数値の大小が記号の個数に直接対応するため、チューリングマシンによる操作（記号の追加・削除）が比較的容易になります。

単項表現における乗算

単項表現における a と b の乗算 a × b は、「単項表現された a の記号列を、b の数だけ繰り返してコピーする」操作と考えることができます。

例： * 00 (2) × 000 (3) * これは、「00」というパターンを 000 (3) の数だけコピーする、と考えられます。 * 結果は 00 + 00 + 00 = 000000 (6) となります。

したがって、チューリングマシンによる単項表現の乗算は、基本的なテープ操作と繰り返し構造によって実現可能であることがわかります。

チューリングマシンによる乗算アルゴリズムの概要

単項表現 A (0が a個) と B (0が b個) の乗算 A × B (0が a×b個) を計算するための基本的なアルゴリズムは以下のようになります。

1. 入力テープに、A と B を区切り記号（例: #）で隔てて配置します。例えば 00#000。結果領域としてテープの末尾などに別途領域を確保することも考えられますが、ここでは入力領域とは別の位置（例えば左端から）に結果を構築することを考えます。入力領域を破壊しながら結果を生成する方法もあります。ここでは、入力 A#B から AB を b 回コピーして結合し、最終的に A × B となる 0 の列を得る戦略を取ります。入力は破壊しても構いません。
2. B の 0 の個数（すなわち b の値）を数えるカウンター、またはその 0 の個数だけ繰り返すための仕組みが必要です。これは、B の 0 を一つずつ消費していくことで実現できます。
3. B の 0 を一つ消費するごとに、A の 0 の列全体を結果領域にコピーします。
4. B の全ての 0 を消費し終えたら、計算完了です。結果領域に残った 0 の列が乗算結果となります。

このアルゴリズムでは、「A のコピー」と「B の 0 を一つずつ処理するための走査」が主要な操作となります。テープ上の区切り記号や特殊記号（コピー済みの印など）を活用しながら、ヘッドを移動させ、状態を遷移させることでこれらの操作を実現します。

シミュレーターでの動作解説（例: 2 × 3）

ここでは、入力 00#000 (2 × 3) を例に、チューリングマシンがどのように動作するかをシミュレーター上で追跡します。簡略化のため、入力はテープ上に _00#000_ のように配置され（_は空白シンボル）、結果は最終的にテープ上に _000000_ と出力されることを目指します。実際の実装では、入力領域をマークしながらコピーし、結果領域を構築することになります。

構成要素の例

• アルファベット: {0, #, X, Y, _, R} (0: 数値の単項表現, #: 区切り, X: コピー元Aのマーク, Y: コピー元Bのマーク, _: 空白, R: 結果領域にコピーされたAのマーク または Aのコピーに使われた一時マーク)
• 状態: q_start (初期状態), q_copy_A (Aをコピー中), q_find_B0 (Bの0を探す), q_copy_A_to_result (Aのシンボルを結果にコピー), q_return_to_A (Aの先頭に戻る), q_rewind_A (コピー元Aのマークをリセット), q_check_B (Bの処理完了確認), q_shift_result (結果をテープの先頭に移動), q_halt (停止状態) など

動作ステップ（簡略化）

1. 初期状態: q_start。ヘッドはテープの左端（例えば最初の0）に位置。テープ: _00#000_
2. Bの0を1つマーク: q_find_B0 状態へ遷移し、#をスキップして最初の 0 (Bの最初の0) を Y に置き換える。テープ: _00#Y00_。この Y が、Bの処理中の1つ目の「0」を示す。
3. Aのコピー開始: q_copy_A 状態へ遷移し、テープの左端（結果領域を構築する場所）へヘッドを移動。
4. Aの0をコピー: q_copy_A_to_result 状態などで、Aの各 0 を順に読み取り、例えば一時的に X に置き換えながら、テープの適切な位置（現在の結果領域の末尾）に 0 を書き込む。
   • テープ: _00#Y00_ -> _X0#Y00_ -> ヘッドを右端に移動し _X0#Y00_0_ -> ヘッドを戻して次の0を処理 -> _XX#Y00_00_
5. Aのコピー完了: Aの全ての 0 を X に置き換えたら、結果領域にAのコピー（00）が書き込まれたことを確認。テープ: _XX#Y00_00_。
6. Aのマークをリセット: q_rewind_A 状態などで、テープ左端に戻り、X を 0 に戻す。これは次のコピーのためにAを元の状態に戻す処理。テープ: _00#Y00_00_。
7. Bの次の0を探す: q_find_B0 状態へ遷移し、# と Y をスキップして、Bの次の 0 を探す。
8. Bの0をマーク (2回目): 次の 0 を Y に置き換える。テープ: _00#YY0_00_。そしてステップ3へ戻り、Aを再びコピー。結果領域に 00 が追加され、テープは _00#YY0_0000_ となる。
9. Bの0をマーク (3回目): 次の 0 を Y に置き換える。テープ: _00#YYY_0000_。そしてステップ3へ戻り、Aを再びコピー。結果領域に 00 が追加され、テープは _00#YYY_000000_ となる。
10. Bの処理完了確認: q_check_B 状態へ遷移し、# 以降に 0 が残っていないかを確認する。全て Y になっている場合（または空白になっている場合）、Bの全ての 0 を処理し終えたと判断。
11. 結果の整形: 必要に応じて、入力領域 (00#YYY) を消去し、結果領域 (000000) をテープの先頭に移動する q_shift_result などの状態を経る。
12. 停止: 整形が完了したら、q_halt 状態へ遷移し停止。最終的なテープの内容が乗算結果となる。テープ: _000000_。

この動作は、チューリングマシンの遷移関数（現在の状態、読み取った記号）→（書き込む記号、ヘッドの移動方向、次の状態）に従って忠実に実行されます。シミュレーター上では、各ステップでのテープの状態、ヘッドの位置、現在の状態がグラフィカルに表示されるため、上記のステップがどのように実現されているかを具体的に確認できます。特に、Aをコピーするためにヘッドが行ったり来たりする様子、Bの0をマークして「処理済み」とする様子、結果領域が徐々に構築されていく様子などが視覚的に把握できるでしょう。

シミュレーターの活用ポイント

本稿で解説した単項表現の乗算チューリングマシンをシミュレーターで実際に動かす際は、以下の点に注目すると理解が深まります。

• 状態遷移図: どのような状態が存在し、どのような条件（テープ上の記号）で状態が遷移するのかを、図と実際の動作を対比させて確認してください。例えば、「Aのコピー中」「Bの次の0を探している状態」などがどのように遷移図上で表現されているかを見てみましょう。
• テープ上のシンボル変化: 0 が X や Y に置き換わるタイミング、結果領域に 0 が書き込まれるタイミングをステップごとに追跡してください。シンボルの変化がアルゴリズムのどの部分に対応しているのかが分かります。
• ヘッドの移動: ヘッドがテープ上をどのように移動しているかを観察してください。コピー操作や、Bの0を探す操作、Aのマークをリセットする操作などが、ヘッドの往復移動として現れます。
• 異なる入力での実験: 0#00 (1 × 2)、000#0 (3 × 1)、#00 (0 × 2 - 0の扱いは実装による)、00##00 (不正な入力) など、様々な入力パターンでシミュレーターを動かし、意図した結果になるか、あるいはどのような動作をするかを確認することで、設計したチューリングマシン（遷移関数）の挙動への理解が深まります。

まとめ

チューリングマシンによる単項表現の乗算は、計算がどのように基本的な機械的操作に分解されるかを示す良い例です。本稿では、アルゴリズムの概要と、入力 00#000 に対するシミュレーター上での具体的な動作ステップを解説しました。

シミュレーターを利用することで、抽象的な遷移関数や状態遷移図が、テープ上の記号変化やヘッドの動きという具体的な動作とどのように結びつくのかを視覚的に理解できます。単項表現の乗算は比較的シンプルですが、これを基盤として、より複雑な計算（例えば二進数での乗算、除算など）もチューリングマシンで実現可能であることが理論的に示されています。

ぜひ、実際にシミュレーターを操作し、本稿で解説した乗算アルゴリズムの実装を確認してみてください。具体的な動作を追体験することが、チューリングマシンの計算能力や限界についてのより深い洞察につながるはずです。