チューリングマシンによる二進数減算の実装：シミュレーターでステップを追う
チューリングマシンは計算の基本的なモデルであり、様々なアルゴリズムを表現できます。本記事では、チューリングマシンを用いて二進数の減算を実装する方法を解説します。計算機科学を学ぶ上で重要な概念であるチューリングマシンの動作を、具体的なアルゴリズムを通して理解し、シミュレーターでの追体験を助けることを目的とします。
チューリングマシンにおける二進数減算の考え方
二進数減算は、人間が紙と鉛筆で行う筆算と似た方法でチューリングマシン上でも実現可能です。基本的な考え方は、最下位桁から順に減算を行い、必要に応じて上位桁から「借り入れ」を行うというものです。チューリングマシンでは、この「借り入れ」の状態を内部状態として保持するか、テープ上の特別な記号でマークすることで処理します。
ここでは、簡単のため、被減数（引かれる数）が減数（引く数）より大きい、符号なし整数の減算を考えます。テープ上には、被減数、区切り記号、減数が並んでいる状態を想定します。例えば、1101 - 101 という計算を考える場合、テープ上の初期配置は ...#1101-101#... のような形になるかもしれません（#は空白記号）。
アルゴリズムの概要
チューリングマシンで二進数減算を行うための基本的なステップは以下のようになります。
- 初期位置へ移動: テープの右端、つまり最も下位の桁の位置にヘッドを移動します。
- 桁ごとの減算: 右端から左（上位桁）に向かって一桁ずつ減算を行います。
- 被減数と減数の対応する桁の記号を読み取ります。
- 現在の桁での借り入れの状態（前の桁から借り入れが必要かどうか）を考慮します。
- これらの情報（被減数の桁、減数の桁、借り入れの状態）に基づき、計算結果の桁（0または1）と、次の桁へ伝えるべき借り入れの状態を決定します。
- 被減数の対応する桁の位置に計算結果を書き込みます。
- 減数の対応する桁の記号は不要になるため、空白などの記号に置き換えます。
- ヘッドを左に移動し、次の桁の処理に移ります。
- 減数がなくなった場合の処理: 減数の桁がなくなった後は、被減数の残りの桁と借り入れの状態だけを考慮して処理を続けます。借り入れが必要であれば、被減数の桁から借り入れを行い、結果を書き込みます。
- 借り入れの伝播: 処理が最も左の桁に達してもなお借り入れが解消されていない場合は、負の結果になるか、または桁あふれが発生する可能性があります。ここでは符号なし減算で被減数 >= 減数を仮定しているため、このような状況は発生しないようにテープ上の数の長さを調整するなど考慮が必要です。
- 結果の整理: 減数部分や一時的に使用した記号などを消去し、テープ上に減算結果だけが残るように整理します。
- 停止: 処理が完了したら、停止状態へ移行します。
具体的な動作例：1101 - 101
例として、1101 から 101 を減算する動作を追ってみましょう。テープの初期状態を ...#1101-101#... とし、結果を被減数の位置に残すようにアルゴリズムを設計します。ヘッドは最初、例えば被減数の右端（1）にいるとします。
| ステップ | 状態 | テープ（ヘッド位置を[]で示す） | 読み取り | 書き込み | 移動方向 | 次の状態 | 処理内容 |
| :------- | :------- | :----------------------------- | :------- | :------- | :------- | :------------------- | :------------------------------------- |
| 0 | Q_init | ...#110[1]-101#... | 1 | - | L | Q_find_separator | 減数との区切りを探しに左へ移動 |
| ... | ... | ...#1101[-]101#... | - | - | R | Q_to_subtrahend_end | 減数の右端へ移動開始 |
| ... | ... | ...#1101-10[1]#... | 1 | - | L | Q_subtraction_start | 減数の右端に到達、減算開始 |
ここから、桁ごとに減算を行います。借り入れの状態を内部状態 (Q_sub_noborrow, Q_sub_borrow) やテープ上のマークで管理します。ここでは状態を使用する例を想定します。減数は処理済みの桁を例えば_でマークします。
最下位桁 (1桁目):
被減数:1、減数:1、借り入れ:なし
1 - 1 = 0。借り入れは不要。結果:0、次状態での借り入れ:なし。
| ステップ | 状態 | テープ（ヘッド） | 読み取り | 書き込み | 移動方向 | 次の状態 | 処理内容 |
| :------- | :--------------------- | :------------------------- | :------- | :------- | :------- | :--------------------------- | :--------------------------- |
| A | Q_subtraction_start | ...#1101-10[1]#... | 1 | _ | L | Q_move_to_subtrahend | 減数の桁を処理済みにし、被減数側へ |
| A+1 | Q_move_to_subtrahend | ...#110[1]-_#... | 1 | - | R | Q_sub_noborrow | 被減数側へ移動完了、借り入れなし状態で減算 |
| A+2 | Q_sub_noborrow | ...#110[1]-_#... | 1 | 0 | L | Q_move_to_subtrahend_next | 減算結果0を書き込み、次の桁へ移動準備 |
| A+3 | Q_move_to_subtrahend_next | ...#11[0]0-_#... | 0 | - | L | Q_find_subtrahend_pos | 次の減算桁の被減数位置を探す |
| ... | ... | ...#11[0]0-_#... | 0 | - | R | Q_find_subtrahend_pos | 減数の処理済み記号_をスキップ |
| ... | ... | ...#1100[-]_#... | - | - | R | Q_move_to_subtrahend_end | 減数の現在の桁位置を探しに右へ |
| ... | ... | ...#1100-_-[]#... | # | - | L | Q_subtraction_start | 減数の現在桁に到達（空白記号） |
2桁目:
被減数:0、減数:0、借り入れ:なし
0 - 0 = 0。借り入れは不要。結果:0、次状態での借り入れ:なし。
同様のステップを経て、被減数の2桁目(0)に0を書き込みます。テープは ...#11[0]0-_ _#... のようになります。
3桁目:
被減数:1、減数:1、借り入れ:なし
1 - 1 = 0。借り入れは不要。結果:0、次状態での借り入れ:なし。
同様のステップを経て、被減数の3桁目(1)に0を書き込みます。テープは ...#1[0]00-_ _#... のようになります。
4桁目:
被減数:1、減数:空白、借り入れ:なし
減数の対応する桁がない場合、その桁は0と見なします。
1 - 0 = 1。借り入れは不要。結果:1、次状態での借り入れ:なし。
同様のステップを経て、被減数の4桁目(1)に1を書き込みます。テープは ...#[1]000-_ _#... のようになります。
減数部分の消去と整理:
減数部分 (-, _) を空白記号 (#) に置き換える処理を行います。ヘッドを左端に移動し、不要な記号を消去します。
| ステップ | 状態 | テープ（ヘッド） | 読み取り | 書き込み | 移動方向 | 次の状態 | 処理内容 |
| :------- | :------------------ | :------------------- | :------- | :------- | :------- | :-------------------- | :----------------------------------------- |
| B | Q_clean | ...#[1]000-_ _#... | 1 | - | L | Q_clean | 左へ移動しながら減数部分を探す |
| ... | ... | ...#1000[-]_ _#... | - | # | R | Q_clean_right | 減数区切りを消去、右へ移動し減数部分を消去 |
| ... | ... | ...#1000##[_]#... | _ | # | R | Q_clean_right | 処理済み減数桁を消去 |
| ... | ... | ...#1000###[]#... | # | - | L | Q_trim_leading_zeros | 整理完了、先頭の不要なゼロを探す |
| ... | ... | ...#[1]000###... | 1 | - | R | Q_accept | 先頭の1に到達、結果は1000、停止状態へ |
最終的にテープには ...#1000#... と結果が残ります。
シミュレーターでの対応
このアルゴリズムをチューリングマシンシミュレーターで実装・実行する際、上記の各ステップはシミュレーター上の以下の要素と対応します。
- 状態 (State):
Q_init,Q_find_separator,Q_subtraction_start,Q_sub_noborrow,Q_sub_borrow(借り入れがある場合の状態),Q_move_to_subtrahend,Q_move_to_subtrahend_next,Q_find_subtrahend_pos,Q_clean,Q_clean_right,Q_trim_leading_zeros,Q_acceptなどが、状態遷移図の各ノードとして表示されます。現在の状態は、シミュレーターの「現在の状態」表示や、状態遷移図上のハイライトで確認できます。 - テープ (Tape): テープの記号の並び全体が表示されます。
...#1101-101#...のような初期状態や、上記のステップ例で示したテープ内容の変化が、シミュレーターのテープ表示エリアに逐次反映されます。 - ヘッド (Head): 現在テープのどのマス目を読み書きしているかが示されます。シミュレーター上では通常、矢印や枠などで示されます。ステップごとのヘッドの移動 (
LまたはR) が視覚的に追えます。 - 遷移関数 (Transition Function): 各ステップでの動作の核です。「現在の状態」と「ヘッドが読み取った記号」の組に対して、「書き込む記号」、「ヘッドの移動方向」、「次の状態」を決定します。これはシミュレーターの状態遷移表として定義し、表示される部分です。上記のステップ例の表の各行が、この遷移関数の一部に対応します。
シミュレーターでこの減算マシンを構築し、ステップ実行機能を使うことで、各状態でのヘッドの動き、テープの内容変化、状態の遷移を視覚的に確認でき、アルゴリズムがどのように計算を実行しているかを深く理解できます。特に、借り入れの状態がどのように次のステップに影響するか、不要な記号がどのように整理されるかといった部分に注目すると良いでしょう。
限界と発展
今回解説した単純な二進数減算マシンは、いくつかの制限があります。
- 符号なし整数: 負の結果になる計算（例:
101 - 1101）や、桁あふれを考慮していません。負の結果を扱うには、2の補数表現など、別の数値表現やより複雑なアルゴリズムが必要です。 - 特定の入力形式: 入力が
被減数-減数の形式であること、被減数と減数の間に適切な区切り記号があることなどを前提としています。汎用的な入力形式に対応するには、入力文字列のパース処理などもマシンに組み込む必要があります。
より高度なチューリングマシンによる演算を実装するには、状態数を増やしたり、テープ上の記号を工夫したりする必要があります。例えば、2の補数を用いた減算や、乗算、除算といったアルゴリズムもチューリングマシンで実現可能ですが、状態遷移はさらに複雑になります。
結論
チューリングマシンによる二進数減算の実装を通して、計算の基本的なステップがいかにプリミティブな操作（読み取り、書き込み、移動、状態遷移）の組み合わせで実現されるかを解説しました。紙上でのアルゴリズム設計と、それをシミュレーター上の具体的な遷移規則やテープ操作に落とし込む作業は、チューリングマシンの計算能力と限界を理解する上で非常に有効です。
ぜひ、本記事で解説した考え方を参考に、ご自身のチューリングマシンシミュレーターで二進数減算マシンを構築し、様々な入力で動作を観察してみてください。抽象的な理論が具体的な動作として目の前に現れることで、理解がより一層深まることと思います。