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

チューリングマシンによる多テープシミュレーション：単一テープでの実現方法と動作例

Tags: チューリングマシン, 計算可能性, 多テープ, 計算量理論, シミュレーション

チューリングマシンは計算理論の基礎をなす抽象的なモデルであり、その最も基本的な形式は単一の無限テープと1つのヘッドを持つものです。しかし、計算のモデルを考える上で、複数のテープを持つ「多テープチューリングマシン」を考えることは自然な拡張です。直感的には、複数のテープを持つ方が単一テープよりも強力な計算能力を持つように感じられるかもしれません。本稿では、この多テープチューリングマシンが単一テープチューリングマシンと計算能力において等価であることを示し、特に、多テープチューリングマシンの動作を単一テープチューリングマシンでどのようにシミュレートできるのかについて解説します。そして、そのシミュレーションの具体的な動作例をシミュレーターでの表示と対応させながら説明します。

多テープチューリングマシンとは

多テープチューリングマシンは、単一テープチューリングマシンとほぼ同じ構成要素を持ちますが、テープとヘッドが複数個（有限個）存在します。各テープには独立したヘッドがあり、各ステップで全てのヘッドが独立に左右に移動したり、それぞれのテープに記号を書き込んだりすることができます。遷移関数は、現在の状態と全てのテープから読み取った記号の組を入力として、次の状態、各テープに書き込む記号の組、そして各ヘッドの移動方向の組を決定します。

多テープチューリングマシンは、並列処理や複数のデータストリームを扱うようなアルゴリズムを記述する際に、単一テープチューリングマシンよりも直感的で容易な場合があります。例えば、文字列のコピーや比較などは、2つのテープがあれば非常に効率的に行えることが想像できます。

単一テープチューリングマシンによる多テープシミュレーションの概要

計算能力の観点から重要な事実は、任意の多テープチューリングマシンは、計算能力において等価な単一テープチューリングマシンによってシミュレート可能であるということです。つまり、多テープチューリングマシンが計算できるものであれば、単一テープチューリングマシンも計算できます（逆もまた真です）。この等価性は、計算可能性理論におけるチューリングマシンの頑健性を示す重要な性質の一つです。

ただし、このシミュレーションは多くの場合、計算時間（ステップ数）において非効率になります。多テープチューリングマシンが$T(n)$ステップで行える計算を、単一テープチューリングマシンが$O((T(n))^2)$ステップでシミュレートできることが知られています。これは、単一テープマシンが複数のテープ上のヘッドの動きを模倣するために、自身のヘッドを何度も左右に走査する必要があるためです。

単一テープ上での多テープの表現

単一テープチューリングマシンが多テープマシンをシミュレートするためには、まず複数のテープの状態を単一のテープ上に記録する必要があります。$k$本のテープを持つ多テープチューリングマシンをシミュレートする場合、単一テープ上では以下のようにテープの状態を表現することが一般的です。

  1. テープの区切り: 単一テープを複数のセクションに分け、それぞれのセクションが多テープマシンの1本のテープに対応するようにします。セクション間は特別な区切り記号（例: #）で区切ります。
  2. ヘッド位置のマーキング: 各セクション（元のテープ）において、ヘッドが現在位置している記号には、特別なマーカー記号（例: ヘッド位置を示すドット . を記号の下に付加するなど）を付けます。

例えば、2本のテープを持つ多テープマシンで、テープ1が ...01[1]0... （ヘッドが真ん中の1上）、テープ2が ...a[b]c... （ヘッドがb上）であったとします。これを単一テープで表現する場合、以下のような形式が考えられます。

...# 0 1. 0 # a b. c #...

ここで、.はヘッドがその記号の上に位置していることを示します。

シミュレーションのステップ

多テープチューリングマシンが1ステップの動作を行う際、単一テープシミュレーターは以下のステップを実行します。

  1. 全ヘッド位置の読み取り:
    • シミュレーターのヘッドをテープの左端から右端まで走査します。
    • 各テープのセクションにおいて、ヘッド位置を示すマーカーが付いた記号（またはその記号とマーカーの組）を読み取ります。
    • 走査が完了した時点で、シミュレーターは多テープマシンの各テープヘッドが読み取っていた記号の組を記憶しています。これは、シミュレーターの状態の一部として保持するか、テープ上の特定の領域に一時的に記録することで実現します。
  2. 遷移の決定:
    • 記憶した記号の組と現在の状態に基づいて、多テープマシンの遷移関数を適用します。
    • これにより、各テープに書き込むべき新しい記号、各ヘッドの移動方向、そして次の状態が決定されます。
  3. テープの更新とヘッド位置の移動:
    • 再びシミュレーターのヘッドをテープの左端から右端まで走査します。
    • 走査中、各テープのセクションにおいて、以前ヘッド位置だった場所を見つけます（マーカーで識別）。
    • その場所の記号を、ステップ2で決定された新しい記号に書き換えます。
    • 古いヘッド位置マーカーを削除します。
    • ステップ2で決定された移動方向（LまたはR）に応じて、新しいヘッド位置にマーカーを付けます。もしテープが無限に広がる可能性がある場合、必要に応じてセクションの左右に空白記号を追加する処理も行います。
  4. 状態の更新:
    • シミュレーターの状態を、ステップ2で決定された多テープマシンの次の状態に更新します。

これらのステップ全体で、単一テープシミュレーターは多テープマシンの1ステップの動作を模倣します。このプロセスは、多テープマシンが停止するまで繰り返されます。

シミュレーターで追う動作例：2本のテープでのコピー

ここでは、2本のテープを持つ多テープチューリングマシンが、テープ1の入力文字列をテープ2にコピーする動作を考え、それを単一テープチューリングマシンがどのようにシミュレートするかを見てみましょう。

元の多テープマシン (Mmulti):

動作の概要: テープ1を左から右へスキャンし、読み取った記号をテープ2の現在位置に書き込み、テープ2のヘッドを右へ移動させる。テープ1の文字列の終端（例えば空白記号）に達したら停止する。

単一テープシミュレーター (Msingle):

Msingleは1本のテープを持ち、以下のような構造でMmultiの2本のテープを表現します。

# [テープ1の内容 ヘッド1位置マーク] # [テープ2の内容 ヘッド2位置マーク] #

例：入力 101 をコピーする場合。

初期状態（シミュレーターテープ）：# .1 0 1 # .B B B # (.はヘッド位置、Bは空白記号)

シミュレーションステップ例（最初の記号 1 をコピーする部分）:

  1. 全ヘッド位置の読み取り:
    • Msingleのヘッドが左から右へ走査。
    • 最初のセクション # .1 0 1 # から、ヘッド1が1上にあることを読み取る。
    • 次のセクション # .B B B # から、ヘッド2がB上にあることを読み取る。
    • Msingleは「状態 q_read, 読み取り記号組 (1, B)」などを内部的に記憶（またはテープに記録）。
  2. 遷移の決定:
    • Mmultiの遷移関数は、状態 q_read で記号組 (1, B) を読み取ったら、テープ1には何もせず、テープ2には記号 1 を書き込み、ヘッド1を右へ、ヘッド2を右へ移動し、状態 q_copy へ遷移すると決定。
  3. テープの更新とヘッド位置の移動:
    • Msingleのヘッドが再び走査。
    • テープ1セクションの.1を見つけ、.を削除。ヘッドを右へ移動し、次の記号0に.を付加 (0.)。
    • テープ2セクションの.Bを見つけ、.を削除。その位置に1を書き込み、ヘッドを右へ移動し、次の記号Bに.を付加 (B.)。
    • Msingleのテープの状態は # 1 0. 1 # 1 B. B # のようになる。
  4. 状態の更新:
    • Msingleの状態を q_copy に更新。

この一連の走査と更新を繰り返すことで、Mmultiの1ステップがMsingleによってシミュレートされます。Msingleのヘッドは、各テープセクションを何度も行き来しながら、ヘッド位置を特定し、記号を読み書きし、マーカーを移動させるという処理を行います。シミュレーター上でこの単一テープマシンの動作を追うと、ヘッドが激しく左右に動きながらテープ全体をスキャンし、少しずつ多テープマシンの状態を更新していく様子が観察できます。

シミュレーターでの確認

本サイトのシミュレーターでは、このような単一テープによる多テープシミュレーションの例を実際に構成し、その動作をステップごとに追うことができます。シミュレーターのテープ上で、セクションの区切り記号やヘッド位置を示すマーカーがどのように変化していくのかを観察することで、抽象的なシミュレーションのアルゴリズムが具体的にどのようにテープ操作として実現されているのかを視覚的に理解することができます。

状態遷移図を見る際には、Msingleの状態が単にMmultiの状態だけでなく、「どのテープのヘッド位置を読み取り中か」「どのテープを更新中か」といったシミュレーションの内部的なステップを表す多くの状態を持つことになる点に注意が必要です。これは、単一テープマシンが多テープマシンの並列的な動きを逐次的に模倣するために必要な複雑さです。

まとめ

多テープチューリングマシンは、複数のデータストリームを扱うアルゴリズムの記述において単一テープマシンよりも直感的ですが、計算能力の点では単一テープマシンと等価です。この等価性は、単一テープマシンが多テープマシンの状態を自身のテープ上に表現し、複雑なテープ操作によってその動作をシミュレートすることで成り立っています。シミュレーションは時間的な効率を犠牲にすることがありますが、チューリングマシンのモデルの頑健性を示す重要な概念です。

シミュレーターを使って、単一テープマシンがどのように複数のテープの状態を管理し、ヘッドの動きや記号の読み書きを模倣しているのかを具体的に追体験することで、計算理論におけるシミュレーションの考え方や、計算能力の等価性がどのように実現されるのかについて、より深い理解を得ることができるでしょう。