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

チューリングマシンによる二進数加算の実装：シミュレーターでステップを追う

はじめに

計算機科学の基礎を学ぶ上で、チューリングマシンは避けて通れない重要な概念です。抽象的なモデルでありながら、計算の限界や可能性を探る上で不可欠な役割を果たします。本記事では、チューリングマシンが具体的にどのような処理を実行できるのかを理解するための一歩として、二進数表現された数の加算を取り上げます。

単項表現による加算は比較的シンプルに実現できますが、現代の計算機で広く使われている二進数表現での加算は、繰り上がり処理など考慮すべき点があり、より実用的かつ興味深いテーマです。本記事では、二進数加算を行うチューリングマシンの設計思想と、シミュレーター上でその動作がどのように実現されるのかを詳細に解説します。

二進数加算の基本

まず、私たちが紙と鉛筆で行う二進数加算の手順を確認します。これはチューリングマシンの動作設計の基礎となります。

例：110 (6) + 101 (5)

  110
+ 101
-----
 1011 (11)

計算は最下位ビット（一番右の桁）から始まり、左へ進みます。各桁では、その桁のビットと（もしあれば）前の桁からの繰り上がりを足し合わせます。

• 0 + 1 = 1、繰り上がりなし
• 1 + 0 = 1、繰り上がりなし
• 1 + 1 = 0、繰り上がり 1
• （繰り上がり 1）+ （何もない） = 1

この「繰り上がり」をどのように記憶し、次の桁の計算に反映させるかが、チューリングマシンでの実現における鍵となります。

チューリングマシンによる二進数加算の設計

二進数加算を行うチューリングマシンを設計するために、以下の要素を定義します。

テープの表現

入力として、加算したい二進数を特定の形式でテープに配置します。ここでは例として #数1+数2= の形式を用います。# はテープの左端マーカー、+ は区切り、= は加算結果を書き始める位置を示します。計算後、= の後に結果が二進数で書き込まれることを目指します。

例: #110+101=B... (Bは空白記号)

アルファベット

テープ上で使用する記号の集合です。 Σ = { 0, 1, +, =, #, B } ここで、B は空白（Blank）記号とします。

状態

チューリングマシンが現在どのような状況にあるかを示す内部状態です。二進数加算では、「繰り上がりがあるか、ないか」を記憶する必要があるため、状態遷移にこの情報を含めることが一般的です。

例として、以下のような状態を考えます。

• q_init: 初期状態。計算開始位置（通常は = の右）へ移動します。
• q_add_no_carry: 繰り上がりなしで加算を実行中の状態。
• q_add_with_carry: 繰り上がりありで加算を実行中の状態。
• q_back_no_carry: 繰り上がりなしで左へ戻り、次の桁へ移動する状態。
• q_back_with_carry: 繰り上がりありで左へ戻り、次の桁へ移動する状態。
• q_adjust: 計算終了後に、不要な記号の削除や整形を行う状態（必要に応じて）。
• q_accept: 受理状態（計算完了）。

遷移関数

現在の状態とヘッドが読み取った記号の組に対して、書き込む記号、ヘッドの移動方向（左 L, 右 R, 動かない S）、次の状態を定めた規則の集合です。これがチューリングマシンの「プログラム」にあたります。

遷移関数の例（一部抜粋）:

• (q_init,=) -> (=, L,q_back_no_carry) :=` を読み取ったら、次の桁（左隣）へ移動し、繰り上がりなしの状態で計算を開始します。
• (q_back_no_carry, 0) -> (0, L, q_back_no_carry) : 加算対象の桁まで左へ移動。
• (q_back_no_carry, +) -> (+, L, q_find_operand2) : + を超えたら、2つ目のオペランドを探しに行きます。
• (q_add_no_carry, (0,0)) -> (0, R, q_back_no_carry) : 現在桁の値の合計が0（0+0 or 0+0+carry0）。結果は0、繰り上がりなし。右へ移動し、次の桁へ。
• (q_add_no_carry, (1,0)) -> (1, R, q_back_no_carry) : 合計が1（1+0 or 0+1）。結果は1、繰り上がりなし。
• (q_add_no_carry, (1,1)) -> (0, R, q_back_with_carry) : 合計が2（1+1）。結果は0、繰り上がりあり。

ここで (0,0), (1,0) などは、テープ上の2つのオペランドの対応する桁の値を同時に読み取るかのように振る舞うための抽象的な表現です。実際の単一テープチューリングマシンでは、一方のオペランドの桁を読み取って状態やテープの補助領域に一時的に記憶し、もう一方のオペランドの対応する桁へ移動してから計算を行う、といったより複雑な手順が必要です。シミュレーターによっては、これを分かりやすくするために複数トラックや複数ヘッドをサポートしている場合もあります。基本的な単一テープ・単一ヘッドのモデルでは、例えば、一方の数の対応する桁をマークして値を覚え、もう一方の数へ移動し、計算後に結果を書き込む場所へ移動し、また次の桁のために左へ戻る、という往復動作が必要になります。

現実的な単一テープでの設計例として、以下のような手順が考えられます。

1. ヘッドを = の右に移動。
2. 左へ移動しながら、= の左の最初の数字（オペランド2の最下位桁）を読み取り、マーク（例: 0を0', 1を1'に変換）して値を記憶（状態または別のテープ領域で）。
3. さらに左へ移動し、+ を超えてオペランド1の対応する桁（= から同じ距離にある桁）を探す。見つけたらその値を読み取り、マークする。
4. 記憶した2つの桁の値と現在の繰り上がり情報に基づき、合計と新しい繰り上がりを計算。
5. 計算結果を書き込むべき位置（元の = の右、計算中の桁に対応する位置）へヘッドを移動させ、結果（0または1）を書き込む。
6. 新しい繰り上がり情報を状態に記憶する。
7. 左へ戻り、マークした桁のマークを元に戻す。
8. 次の桁の計算のために、再度 = の右隣（今書き込んだ結果の左隣）へ移動し、ステップ2から繰り返す。
9. 両方のオペランドのすべての桁を処理し終え、繰り上がりもなくなったら計算終了。

シミュレーターによっては、このような複雑な単一テープの往復動作を視覚的に追うことで、チューリングマシンの動作の仕組みを深く理解できます。

シミュレーターによる動作例

具体的な入力テープ #110+101= に対して、設計したチューリングマシンがどのように動作するかをシミュレーターで追ってみましょう。

初期状態: テープ: #, 1, 1, 0, +, 1, 0, 1, =, B, B, ... 状態: q_init ヘッド位置: # の上

1. q_init 状態で右へ移動し、= を探します。 ... ヘッドが = の位置へ移動 ... テープ: #, 1, 1, 0, +, 1, 0, 1, =, B, B, ... 状態: q_init ヘッド位置: = の上
2. (q_init,=) -> (=, L,q_back_no_carry) テープ:#,1,1,0,+,1,0,1,=,B,B, ... 状態:q_back_no_carry(繰り上がりなし) ヘッド位置:1` (オペランド2の最下位桁) の上
3. 単一テープモデルの往復動作を開始します。
   • (q_back_no_carry, 1) -> ヘッドを左へ移動、オペランド1の対応桁を探す状態へ遷移。（例: q_find_operand1_val1）
   • ... + を超え、オペランド1の最下位桁 0 を発見 ...
   • ... 0 と 1 (記憶しておいた) を加算 (0+1+carry0=1, carry0)。結果 1 を計算結果位置（= の右隣）に書き込む状態へ遷移 ...
   • ... ヘッドを右へ移動し、= の右隣の B の位置へ ...
   • (q_write_result_1, B) -> (1, L, q_back_for_next_digit_no_carry) : 結果 1 を書き込み、次の桁のために左へ戻る状態へ遷移。 テープ: #, 1, 1, 0, +, 1, 0, 1, =, 1, B, ... 状態: q_back_for_next_digit_no_carry ヘッド位置: = の上
4. 同様の往復動作を次の桁（オペランド2の 0 とオペランド1の 1）に対して繰り返します。今回は 1+0+carry0=1, carry0 なので、結果 1 を 1 の左隣に書き込みます。 テープ: #, 1, 1, 0, +, 1, 0, 1, =, 1, 1, B, ... 状態: q_back_for_next_digit_no_carry ヘッド位置: = の上
5. 次の桁（オペランド2の 1 とオペランド1の 1）に対して繰り返します。今回は 1+1+carry0=0, carry1 なので、結果 0 を 1 の左隣に書き込みます。次の計算は繰り上がりありの状態で行われます。 テープ: #, 1, 1, 0, +, 1, 0, 1, =, 0, 1, 1, B, ... 状態: q_back_for_next_digit_with_carry ヘッド位置: = の上
6. 両方のオペランドの数字をすべて処理し終えた後、繰り上がり 1 が残っています。この繰り上がりを結果の最も左に書き込みます。 テープ: #, 1, 1, 0, +, 1, 0, 1, =, 1, 0, 1, 1, B, ... 状態: q_adjust (整形状態など) ヘッド位置: # の上など
7. 不要なマークなどを削除し、整形が完了したら q_accept 状態へ遷移します。 テープ: #, 1, 1, 0, +, 1, 0, 1, =, 1, 0, 1, 1, B, ... 状態: q_accept ヘッド位置: どこでも良い（例: = の上）

シミュレーターで上記のようなステップを実際に追うことで、抽象的な遷移規則がテープ上の記号の書き換えやヘッドの移動という具体的な動作に繋がり、最終的な計算結果が得られるプロセスを視覚的に理解できます。特に、単一テープモデルでの往復動作による情報のやり取りや、状態による繰り上がりの記憶といった工夫がどのように機能しているのかを把握できます。

設計上の考慮事項と限界

この二進数加算チューリングマシンの設計には、いくつかの考慮事項があります。

• 入力形式: #数1+数2= という固定形式を仮定しています。異なる形式に対応するには、より複雑な前処理または認識機構が必要です。
• 数値の大きさ: テープは無限ですが、計算時間や状態数は有限であるため、実際には計算可能な数値の大きさに実質的な限界があります。特に単一テープでの往復動作は効率が悪く、大きな数の計算には時間がかかります。
• エラー処理: 入力が指定された二進数形式に従わない場合のエラー処理は考慮していません。

これらの限界は、チューリングマシンのモデルそのものの特性や、特定のアルゴリズムをそのモデル上で実現する際のトレードオフを示唆しています。

まとめ

本記事では、チューリングマシンが二進数表現の加算を実行する仕組みについて、その設計思想と具体的な動作例を通して解説しました。特に、繰り上がり処理を状態やテープ操作で実現する方法や、単一テープモデルでの往復によるデータ処理の必要性を示しました。

このような具体的なアルゴリズムの実装例をチューリングマシンシミュレーターで動かしてみることは、計算理論の学習において非常に有効です。抽象的な概念としての遷移関数や状態が、テープ上の記号操作という具体的なステップに分解され、最終的に計算結果が得られるまでのプロセスを視覚的に確認できます。

ぜひ、お手元のチューリングマシンシミュレーターで、今回解説した二進数加算の原理を応用した機械を構築し、様々な入力で動作を試してみてください。理論と実践を結びつけることで、チューリングマシン、ひいては計算という概念への理解がより一層深まることでしょう。