チューリングマシンによる単項表現の減算：シミュレーターで理解するアルゴリズム
チューリングマシンの理論は、計算の可能性と限界を探る上で非常に重要な基盤を提供します。これまでの記事では、チューリングマシンの基本的な構成要素や、コピー、特定の記号の変換、加算といった比較的単純な処理の実装例を解説し、シミュレーター上での動作を追ってきました。本記事では、もう少し複雑な算術演算である「減算」をチューリングマシンでどのように実現するかを、単項表現を用いた例で詳しく解説します。単項表現を用いることで、数値そのものよりも、数値の量をテープ上の記号の個数として直感的に扱うことができます。
単項表現とは
単項表現（Unary representation）とは、数値を1種類の記号（例えば 1）の繰り返しで表現する方法です。例えば、数値の 3 は 111、5 は 11111 と表現されます。この表現方法では、記号の個数がそのまま数値に対応します。
減算 n - m は、テープ上に n を表す記号の列と m を表す記号の列が区切り記号（例えば #）を挟んで配置されている状態から開始し、最終的に n - m を表す記号の列を残す、という処理として定義できます。ただし、n < m の場合は、結果を 0 とするなどの特別な規則を設ける必要があります。ここでは、簡単のため n >= m の場合を考えます。入力形式は 1...1#1...1 (n個の1 # m個の1) とします。
チューリングマシンによる単項減算のアルゴリズム
単項表現での減算 1...1#1...1 (n個の1 # m個の1) のアルゴリズムは、直感的には以下のような手順で実現できます。
- 左側の
1を一つ見つけ、別の記号（例えばX）に書き換える。 - 区切り記号
#を超えて、右側の1を一つ見つけ、別の記号（例えばY）に書き換える。 - テープの左端に戻る。
- これらの手順を、右側の
1が全てYに変わるまで繰り返す。
右側の 1 が全て Y に変わった時点で、左側の 1 のうち m 個が X に書き換えられています。残った X と #、そして右側の Y を適切に処理して、残った 1 (これは n - m 個) だけを残します。
より詳細なステップとしては、以下のようになります。
- 初期状態: テープには
B1...1#1...1B（Bは空白記号）のような文字列が書かれていると仮定します。ヘッドは通常、一番左の非空白記号の上にあります。 - ステップ1: 左端の
1をXに書き換え、右へ移動します。 - ステップ2: 右へ移動し、
#をスキップして最初の1を探します。 - ステップ3: 見つけた
1をYに書き換え、左へ移動します。 - ステップ4: 左へ移動し、
#をスキップしてXを探します。 - ステップ5: 見つけた
Xの右にある1（つまり、次にXに変えるべき1）の上に移動します。 - ステップ6: ステップ1に戻り、左側の
1をXに書き換える処理を繰り返します。 - 終了条件: 右側の
1が全てYに書き換えられたことを検出したら、繰り返しを終了します。これは、ステップ2で#の右に1が見つからずYまたは空白記号Bに遭遇した場合に判断できます。 - 後処理: 右側の
1がなくなった後、テープ上にはXB...X#Y...YBのような状態が残っています。残ったX、#、Yを空白記号Bに書き換えながら、残った1の列をテープの先頭に移動させ、不要な記号を削除します。最終的に、1...1B(n-m個の1) の形式にするには、さらに左寄せなどの処理が必要ですが、ここでは残った1の個数で結果が得られたと判断することも可能です。シミュレーターで動作確認する際は、後処理をどこまで実装するかを定義します。簡単な実装としては、XとYをBに置き換え、残った1をそのままにしておく、というものも考えられます。ここでは、残った1以外を空白に置き換える、という後処理を考えます。
シミュレーターでの動作確認
このアルゴリズムをチューリングマシンシミュレーターで実装し、例えば 4 - 2、つまり 1111#11 という入力で動作を追ってみましょう。
状態と遷移の例
以下に、上記アルゴリズムの一部を実装するための状態遷移の概念的な例を示します。実際のシミュレーターでは、アルファベットや状態名、遷移の詳細な定義が必要です。
-
状態
q0(初期状態): 左端の1を探す。1を読んだら:Xに書き換え、右へ移動。状態q1へ遷移。#を読んだら: (減算対象がないケースなど、エラーまたは終了処理へ)Bを読んだら: (入力形式エラーまたは終了)
-
状態
q1(右側の1を探す):#を越えて最初の1を探す。1を読んだら:Yに書き換え、左へ移動。状態q2へ遷移。Xを読んだら: 右へ移動。(これはスキップすべきではない記号だが、例として)#を読んだら: 右へ移動。Yを読んだら: (右側の1がもう無い、つまり減算完了) 終了処理の状態q3へ遷移。Bを読んだら: (右側の1がもう無い) 終了処理の状態q3へ遷移。
-
状態
q2(左側のXを探す):#を越えて左方向へ移動し、Xを探す。1を読んだら: 左へ移動。Yを読んだら: 左へ移動。#を読んだら: 左へ移動。Xを読んだら: 右へ移動。（次の処理対象の1の上に移動）状態q0へ遷移。Bを読んだら: (最初のXより左に行ってしまった) エラーまたは特殊な終了処理へ。
-
状態
q3(後処理): 残ったX,#,YをBに書き換える。Xを読んだら:Bに書き換え、右へ移動。状態q3を維持。Yを読んだら:Bに書き換え、右へ移動。状態q3を維持。#を読んだら:Bに書き換え、右へ移動。状態q3を維持。1を読んだら: 右へ移動。状態q3を維持。(最終結果として残す)Bを読んだら: 停止状態qhへ遷移。
これは簡略化された例であり、実際の実装ではテープの端の処理や、n < m の場合の処理なども考慮する必要があります。
1111#11 の実行トレース例
入力: B 1 1 1 1 # 1 1 B (ヘッドは一番左の 1)
- q0, 1 -> X, R, q1:
B X 1 1 1 # 1 1 B(ヘッドは次の1) - q1, 1 -> R, q1:
B X 1 1 1 # 1 1 B(ヘッドは次の1) - ... ヘッドは
#を越えて右へ移動 ... - q1, # -> R, q1:
B X 1 1 1 # 1 1 B(ヘッドは#の右の1) - q1, 1 -> Y, L, q2:
B X 1 1 1 # Y 1 B(ヘッドは#) - q2, # -> L, q2:
B X 1 1 1 # Y 1 B(ヘッドは左の1) - ... ヘッドは左へ移動 ...
- q2, X -> R, q0:
B X 1 1 1 # Y 1 B(ヘッドはXの右の1) - q0, 1 -> X, R, q1:
B X X 1 1 # Y 1 B(ヘッドは次の1) - ... ヘッドは
#を越えて右へ移動 ... - q1, # -> R, q1:
B X X 1 1 # Y 1 B(ヘッドは#の右の1) - q1, 1 -> Y, L, q2:
B X X 1 1 # Y Y B(ヘッドは#) - ... ヘッドは左へ移動 ...
- q2, X -> R, q0:
B X X 1 1 # Y Y B(ヘッドはXの右の1) - q0, 1 -> X, R, q1:
B X X X 1 # Y Y B(ヘッドは次の1) - ... ヘッドは
#を越えて右へ移動 ... - q1, # -> R, q1:
B X X X 1 # Y Y B(ヘッドは#の右のY) - q1, Y -> R, q3:
B X X X 1 # Y Y B(ヘッドは右のY) - q3, Y -> B, R, q3:
B X X X 1 # B Y B(ヘッドは右のB) - q3, B -> B, R, q3: (ヘッドは空白。右に移動)
B X X X 1 # B B B(ヘッドは空白) - ... 右方向への後処理 ...
#,Y,Yが順にBに書き換えられる ... - q3, X -> B, R, q3:
B B X X 1 B B B B(ヘッドは次のX) - q3, X -> B, R, q3:
B B B X 1 B B B B(ヘッドは次のX) - q3, X -> B, R, q3:
B B B B 1 B B B B(ヘッドは1) - q3, 1 -> R, q3:
B B B B 1 B B B B(ヘッドは右のB) - q3, B -> B, R, qh:
B B B B 1 B B B B(ヘッドは右のB)
停止状態 qh に到達。テープには B B B B 1 B B B B が残っています。初期位置や後処理の実装によっては、残った 1 がテープの先頭に寄せられたり、空白記号の配置が異なったりしますが、重要なのは 1 が n-m 個（ここでは 4-2=2 個）残っていることです。上記の例では X に変える処理を3回（n回）行っていますが、これはアルゴリズムの説明間違いです。正しくは、左の1と右の1をペアで消していく、つまり m回繰り返す必要があります。
修正後のアルゴリズム概念
- 左端から最初の
1をXに変え、右へ。 #を超えて最初の1をYに変え、左へ。#を超えて最初のXを探してその右へ。このペアリング処理をm回繰り返す。m回目のYへの書き換え後、左へ戻る際に#の右に1がもう見つからないことを検出。- 検出後、後処理状態へ遷移。テープに残った
XとY、そして#を空白Bに変える。
修正後の 1111#11 の実行トレース例
入力: B 1 1 1 1 # 1 1 B (ヘッドは一番左の 1)
- q0, 1 -> X, R, q1:
B X 1 1 1 # 1 1 B(ヘッドは次の1) - ...
q1で#を越えて右へ ... - q1, 1 -> Y, L, q2:
B X 1 1 1 # Y 1 B(ヘッドは#) - ...
q2で#を越えて左へ ... -
q2, X -> R, q0:
B X 1 1 1 # Y 1 B(ヘッドはXの右の1) - 1回目のペアリング終了 -
q0, 1 -> X, R, q1:
B X X 1 1 # Y 1 B(ヘッドは次の1) - ...
q1で#を越えて右へ ... - q1, 1 -> Y, L, q2:
B X X 1 1 # Y Y B(ヘッドは#) - ...
q2で#を越えて左へ ... -
q2, X -> R, q0:
B X X 1 1 # Y Y B(ヘッドはXの右の1) - 2回目のペアリング終了 -
q0, 1 -> X, R, q1:
B X X X 1 # Y Y B(ヘッドは次の1) - ...
q1で#を越えて右へ ... - q1, Y -> R, q3:
B X X X 1 # Y Y B(ヘッドはYに遭遇、右側の1が尽きたことを検出。後処理へ) (ヘッドは右のY) - q3, Y -> B, R, q3:
B X X X 1 # B Y B(ヘッドは右のY) - q3, Y -> B, R, q3:
B X X X 1 # B B B(ヘッドは右のB) -
q3, B -> B, L, q4:
B X X X 1 # B B B(後処理終了。左端に戻るなどの最終処理へ。状態q4(最終整理状態) へ遷移) -
q4, B -> R, q4: (左端まで戻る) ...
- q4, X -> B, R, q4:
B B X X 1 B B B B(ヘッドは次のX) - q4, X -> B, R, q4:
B B B X 1 B B B B(ヘッドは次のX) - q4, X -> B, R, q4:
B B B B 1 B B B B(ヘッドは1) - q4, 1 -> R, q4:
B B B B 1 B B B B(ヘッドは右のB) - q4, B -> B, R, qh:
B B B B 1 B B B B(ヘッドは右のB) - 停止
このトレースでは、後処理で X, #, Y を B に置き換え、残った 1 (2個) がテープ上に表示されています。シミュレーターでは、これらの状態遷移とテープの内容変化が視覚的に表示されるため、アルゴリズムの各ステップがどのように計算に寄与しているかを具体的に理解することができます。
まとめ
本記事では、チューリングマシンを用いて単項表現の減算を行うアルゴリズムの概念と、そのシミュレーター上での動作イメージを解説しました。単項表現を用いることで、数値の操作がテープ上の記号の個数の操作として直感的に捉えられ、チューリングマシンの基本的な動作（記号の読み書き、ヘッドの移動、状態遷移）の組み合わせで比較的複雑な計算が実現できることが分かりました。
シミュレーター上でこのアルゴリズムを実際に定義し、ステップ実行機能を使ってテープの内容やヘッドの位置、現在の状態がどのように変化していくかを観察することで、抽象的なアルゴリズムが具体的な機械の動作としてどのように実装されるかについての理解を一層深めることができるでしょう。異なる入力（例えば 111#1 や 11#11）で試してみることも、理解を助ける良い方法です。計算可能性理論におけるチューリングマシンの位置づけやその能力について学ぶ上で、このような具体的な実装例を追う経験は非常に有益です。