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

チューリングマシンによる単項表現の減算:シミュレーターで理解するアルゴリズム

Tags: チューリングマシン, 計算理論, アルゴリズム, 減算, 単項表現, シミュレーション

チューリングマシンの理論は、計算の可能性と限界を探る上で非常に重要な基盤を提供します。これまでの記事では、チューリングマシンの基本的な構成要素や、コピー、特定の記号の変換、加算といった比較的単純な処理の実装例を解説し、シミュレーター上での動作を追ってきました。本記事では、もう少し複雑な算術演算である「減算」をチューリングマシンでどのように実現するかを、単項表現を用いた例で詳しく解説します。単項表現を用いることで、数値そのものよりも、数値の量をテープ上の記号の個数として直感的に扱うことができます。

単項表現とは

単項表現(Unary representation)とは、数値を1種類の記号(例えば 1)の繰り返しで表現する方法です。例えば、数値の 3111511111 と表現されます。この表現方法では、記号の個数がそのまま数値に対応します。

減算 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. 左側の 1 を一つ見つけ、別の記号(例えば X)に書き換える。
  2. 区切り記号 # を超えて、右側の 1 を一つ見つけ、別の記号(例えば Y)に書き換える。
  3. テープの左端に戻る。
  4. これらの手順を、右側の 1 が全て Y に変わるまで繰り返す。

右側の 1 が全て Y に変わった時点で、左側の 1 のうち m 個が X に書き換えられています。残った X#、そして右側の Y を適切に処理して、残った 1 (これは n - m 個) だけを残します。

より詳細なステップとしては、以下のようになります。

シミュレーターでの動作確認

このアルゴリズムをチューリングマシンシミュレーターで実装し、例えば 4 - 2、つまり 1111#11 という入力で動作を追ってみましょう。

状態と遷移の例

以下に、上記アルゴリズムの一部を実装するための状態遷移の概念的な例を示します。実際のシミュレーターでは、アルファベットや状態名、遷移の詳細な定義が必要です。

これは簡略化された例であり、実際の実装ではテープの端の処理や、n < m の場合の処理なども考慮する必要があります。

1111#11 の実行トレース例

入力: B 1 1 1 1 # 1 1 B (ヘッドは一番左の 1)

  1. q0, 1 -> X, R, q1: B X 1 1 1 # 1 1 B (ヘッドは次の 1)
  2. q1, 1 -> R, q1: B X 1 1 1 # 1 1 B (ヘッドは次の 1)
  3. ... ヘッドは # を越えて右へ移動 ...
  4. q1, # -> R, q1: B X 1 1 1 # 1 1 B (ヘッドは # の右の 1)
  5. q1, 1 -> Y, L, q2: B X 1 1 1 # Y 1 B (ヘッドは #)
  6. q2, # -> L, q2: B X 1 1 1 # Y 1 B (ヘッドは左の 1)
  7. ... ヘッドは左へ移動 ...
  8. q2, X -> R, q0: B X 1 1 1 # Y 1 B (ヘッドは X の右の 1)
  9. q0, 1 -> X, R, q1: B X X 1 1 # Y 1 B (ヘッドは次の 1)
  10. ... ヘッドは # を越えて右へ移動 ...
  11. q1, # -> R, q1: B X X 1 1 # Y 1 B (ヘッドは # の右の 1)
  12. q1, 1 -> Y, L, q2: B X X 1 1 # Y Y B (ヘッドは #)
  13. ... ヘッドは左へ移動 ...
  14. q2, X -> R, q0: B X X 1 1 # Y Y B (ヘッドは X の右の 1)
  15. q0, 1 -> X, R, q1: B X X X 1 # Y Y B (ヘッドは次の 1)
  16. ... ヘッドは # を越えて右へ移動 ...
  17. q1, # -> R, q1: B X X X 1 # Y Y B (ヘッドは # の右の Y)
  18. q1, Y -> R, q3: B X X X 1 # Y Y B (ヘッドは右の Y)
  19. q3, Y -> B, R, q3: B X X X 1 # B Y B (ヘッドは右の B)
  20. q3, B -> B, R, q3: (ヘッドは空白。右に移動) B X X X 1 # B B B (ヘッドは空白)
  21. ... 右方向への後処理 ... #, Y, Y が順に B に書き換えられる ...
  22. q3, X -> B, R, q3: B B X X 1 B B B B (ヘッドは次の X)
  23. q3, X -> B, R, q3: B B B X 1 B B B B (ヘッドは次の X)
  24. q3, X -> B, R, q3: B B B B 1 B B B B (ヘッドは 1)
  25. q3, 1 -> R, q3: B B B B 1 B B B B (ヘッドは右の B)
  26. 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 がテープの先頭に寄せられたり、空白記号の配置が異なったりしますが、重要なのは 1n-m 個(ここでは 4-2=2 個)残っていることです。上記の例では X に変える処理を3回(n回)行っていますが、これはアルゴリズムの説明間違いです。正しくは、左の1と右の1をペアで消していく、つまり m回繰り返す必要があります。

修正後のアルゴリズム概念

  1. 左端から最初の 1X に変え、右へ。
  2. # を超えて最初の 1Y に変え、左へ。
  3. # を超えて最初の X を探してその右へ。このペアリング処理を m 回繰り返す。
  4. m 回目の Y への書き換え後、左へ戻る際に # の右に 1 がもう見つからないことを検出。
  5. 検出後、後処理状態へ遷移。テープに残った XY、そして # を空白 B に変える。

修正後の 1111#11 の実行トレース例

入力: B 1 1 1 1 # 1 1 B (ヘッドは一番左の 1)

  1. q0, 1 -> X, R, q1: B X 1 1 1 # 1 1 B (ヘッドは次の 1)
  2. ... q1# を越えて右へ ...
  3. q1, 1 -> Y, L, q2: B X 1 1 1 # Y 1 B (ヘッドは #)
  4. ... q2# を越えて左へ ...
  5. q2, X -> R, q0: B X 1 1 1 # Y 1 B (ヘッドは X の右の 1) - 1回目のペアリング終了

  6. q0, 1 -> X, R, q1: B X X 1 1 # Y 1 B (ヘッドは次の 1)

  7. ... q1# を越えて右へ ...
  8. q1, 1 -> Y, L, q2: B X X 1 1 # Y Y B (ヘッドは #)
  9. ... q2# を越えて左へ ...
  10. q2, X -> R, q0: B X X 1 1 # Y Y B (ヘッドは X の右の 1) - 2回目のペアリング終了

  11. q0, 1 -> X, R, q1: B X X X 1 # Y Y B (ヘッドは次の 1)

  12. ... q1# を越えて右へ ...
  13. q1, Y -> R, q3: B X X X 1 # Y Y B (ヘッドは Y に遭遇、右側の 1 が尽きたことを検出。後処理へ) (ヘッドは右の Y)
  14. q3, Y -> B, R, q3: B X X X 1 # B Y B (ヘッドは右の Y)
  15. q3, Y -> B, R, q3: B X X X 1 # B B B (ヘッドは右の B)
  16. q3, B -> B, L, q4: B X X X 1 # B B B (後処理終了。左端に戻るなどの最終処理へ。状態 q4 (最終整理状態) へ遷移)

  17. q4, B -> R, q4: (左端まで戻る) ...

  18. q4, X -> B, R, q4: B B X X 1 B B B B (ヘッドは次の X)
  19. q4, X -> B, R, q4: B B B X 1 B B B B (ヘッドは次の X)
  20. q4, X -> B, R, q4: B B B B 1 B B B B (ヘッドは 1)
  21. q4, 1 -> R, q4: B B B B 1 B B B B (ヘッドは右の B)
  22. q4, B -> B, R, qh: B B B B 1 B B B B (ヘッドは右の B) - 停止

このトレースでは、後処理で X, #, YB に置き換え、残った 1 (2個) がテープ上に表示されています。シミュレーターでは、これらの状態遷移とテープの内容変化が視覚的に表示されるため、アルゴリズムの各ステップがどのように計算に寄与しているかを具体的に理解することができます。

まとめ

本記事では、チューリングマシンを用いて単項表現の減算を行うアルゴリズムの概念と、そのシミュレーター上での動作イメージを解説しました。単項表現を用いることで、数値の操作がテープ上の記号の個数の操作として直感的に捉えられ、チューリングマシンの基本的な動作(記号の読み書き、ヘッドの移動、状態遷移)の組み合わせで比較的複雑な計算が実現できることが分かりました。

シミュレーター上でこのアルゴリズムを実際に定義し、ステップ実行機能を使ってテープの内容やヘッドの位置、現在の状態がどのように変化していくかを観察することで、抽象的なアルゴリズムが具体的な機械の動作としてどのように実装されるかについての理解を一層深めることができるでしょう。異なる入力(例えば 111#111#11)で試してみることも、理解を助ける良い方法です。計算可能性理論におけるチューリングマシンの位置づけやその能力について学ぶ上で、このような具体的な実装例を追う経験は非常に有益です。