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

計算可能性理論入門：原始帰納的関数をチューリングマシンで実現する方法

Tags: 計算可能性理論, 原始帰納的関数, チューリングマシン, シミュレーション, 計算可能性

チューリングマシンは計算機科学における最も基本的な計算モデルの一つであり、計算可能性理論の中心的な役割を果たしています。この理論では、「どのような計算が可能か」あるいは「どのような関数が計算可能か」を探求します。本記事では、計算可能な関数の重要なサブクラスである「原始帰納的関数」に焦点を当て、これらの関数がチューリングマシンによって計算可能であることを、基本的な構成要素に分解して解説します。チューリングマシンシミュレーターを用いることで、抽象的な定義が具体的な動作としてどのように実現されるかを視覚的に理解することが可能になります。

原始帰納的関数とは

原始帰納的関数（Primitive Recursive Function）は、特定の基本的な関数と、それらを組み合わせるための規則（合成と原始再帰）を用いて定義される関数のクラスです。計算可能性理論において、多くの「実際に計算できる」関数は原始帰納的関数に含まれます。

原始帰納的関数は以下の基本的な関数から出発し、以下の構成規則を有限回適用して得られる関数として定義されます。

基本関数

  1. ゼロ関数 Z(x): 任意の入力 x に対して 0 を返します。すなわち、Z(x) = 0 です。
  2. サクセサ関数 S(x): 入力 x に対して x + 1 を返します。すなわち、S(x) = x + 1 です。
  3. 射影関数 P_i^n(x_1, ..., x_n): n個の入力 (x_1, ..., x_n) に対して、i番目の入力 x_i を返します (1 ≤ i ≤ n)。

構成規則

  1. 合成 (Composition): 関数 f(y_1, ..., y_m) と、関数 g_1(x_1, ..., x_n), ..., g_m(x_1, ..., x_n) が原始帰納的関数であるとき、これらの合成 h(x_1, ..., x_n) = f(g_1(x_1, ..., x_n), ..., g_m(x_1, ..., x_n)) も原始帰納的関数です。
  2. 原始再帰 (Primitive Recursion): n変数関数 g と (n+2)変数関数 h が原始帰納的関数であるとき、以下の2つの条件を満たす (n+1)変数関数 f も原始帰納的関数です。
    • f(x_1, ..., x_n, 0) = g(x_1, ..., x_n)
    • f(x_1, ..., x_n, y+1) = h(x_1, ..., x_n, y, f(x_1, ..., x_n, y))

チューリングマシンによる基本関数の実現

原始帰納的関数の基本関数は、チューリングマシンによって容易に計算可能です。シミュレーター上での実現を考慮し、入力はテープ上に単項表現（例: 数値 k を '1' が k 個並んだ列で表現）として与えられ、隣接する入力間は区切り文字（例: '#'）で区切られていると仮定します。出力も同様に単項表現でテープ上に生成されます。

ゼロ関数 Z(x) の実現

Z(x) = 0 は、入力 x の値に関わらず 0 を出力します。これは、テープ上の入力領域をすべて空白記号で上書きするか、または特定のセルに '0' などを書き込み、ヘッドを初期位置に戻して停止するチューリングマシンで実現できます。

シミュレーターでの動作例: 1. 初期状態 q0 でヘッドが入力の先頭に位置します。 2. ヘッドを右に移動させながら、入力記号（'1' や区切り文字 '#'）をすべて空白記号（または特定の出力記号 '0'）に書き換えます。 3. 空白記号を読み込んだら（テープの終端）、左に移動を開始します。 4. テープの先頭（または特定の開始マーカー）に戻ったら停止状態 q_accept に遷移します。

サクセサ関数 S(x) の実現

S(x) = x + 1 は、入力 x に 1 を加えます。入力 x を単項表現（'1'が x 個）とすると、出力は '1'が x+1 個並んだ列になります。これは、入力の末尾に '1' を一つ書き加えるチューリングマシンで実現できます。

シミュレーターでの動作例: 1. 初期状態 q0 でヘッドが入力の先頭に位置します。 2. ヘッドを右に移動させ、入力の終端（最初の空白記号）を探します。 3. 空白記号を読み込んだら、そのセルに '1' を書き込みます。 4. 停止状態 q_accept に遷移します。

射影関数 P_i^n(x_1, ..., x_n) の実現

P_i^n(x_1, ..., x_n) = x_i は、複数の入力から i 番目の入力を取り出します。入力 (x_1, ..., x_n) がテープ上に区切り文字 '#' で区切られて並んでいる場合を考えます。例えば P_2^3(x_1, x_2, x_3) を計算する場合、2番目の入力 x_2 を取り出す必要があります。

シミュレーターでの動作例（P_2^3(x_1, x_2, x_3) の場合）: 1. 初期状態 q0 でヘッドが入力の先頭に位置します。 2. 1番目の入力 x_1 をスキップするため、最初の区切り文字 '#' までヘッドを右に移動します。 3. 最初の '#' を読み込んだら、2番目の入力 x_2 の開始位置に移動します。状態を遷移させて、今度は x_2 の内容を「読み取る」モードに入ります。 4. x_2 の内容を新しい領域にコピーするか、または x_1 と x_3 の領域を消去して x_2 の領域だけを残すようにテープを操作します。 5. テープ上の他の領域を整理し、出力（x_2）のみが残るようにします。 6. 停止状態 q_accept に遷移します。

チューリングマシンによる構成規則の実現

合成と原始再帰といった構成規則自体を直接一つのチューリングマシンとして表現するのは複雑ですが、これらの規則によって定義される任意の関数がチューリングマシンで計算可能であることを示すことができます。これは、より単純な関数を計算するチューリングマシンを「サブルーチン」のように組み合わせることで実現されると考えることができます。

合成の実現

h(x_1, ..., x_n) = f(g_1(x_1, ..., x_n), ..., g_m(x_1, ..., x_n)) の計算は、以下のステップを逐次的に実行するチューリングマシンとして構成できます。

  1. 入力 (x_1, ..., x_n) がテープ上に与えられます。
  2. g_1 を計算するチューリングマシンを実行し、結果 y_1 をテープ上の別の領域に書き出します。
  3. g_2 を計算するチューリングマシンを実行し、結果 y_2 をテープ上の別の領域に書き出します。
  4. ...
  5. g_m を計算するチューリングマシンを実行し、結果 y_m をテープ上の別の領域に書き出します。
  6. テープ上の y_1, ..., y_m を新しい入力として、f を計算するチューリングマシンを実行します。
  7. f の計算結果が最終的な出力となります。

これは、複数のチューリングマシンを直列に接続し、テープを中間結果の受け渡しに使うイメージです。単一テープチューリングマシンでも、テープ上の異なる領域を使ってこれらの操作を模倣することが可能です。シミュレーター上では、このような多段階の計算を定義することで合成関数を表現できます。

原始再帰の実現

f(x, 0) = g(x) および f(x, y+1) = h(x, y, f(x, y)) で定義される原始再帰による関数 f の計算は、繰り返し構造を用いてチューリングマシンで実現できます。

計算 f(x, y) を行うために、チューリングマシンは以下の操作を行います。

  1. まず f(x, 0) = g(x) を計算します。これは g を計算するTMを実行することで得られます。結果をテープに保存します。
  2. 次に、f(x, 1) を計算するために、保存した f(x, 0) の結果と h の定義を利用します。具体的には h(x, 0, f(x, 0)) を計算します。これは h を計算するTMを実行することで得られます。結果をテープに保存し、f(x, 0) の結果は不要であれば消去します。
  3. このプロセスを y 回繰り返します。f(x, y'+1) を計算する際には、常に直前の結果 f(x, y') を利用し、h を適用します。

この繰り返しは、カウンターとして y の値を管理し、その値が 0 になるまで特定の計算ブロック（h の計算部分）を繰り返し実行するチューリングマシンとして実現可能です。テープは、入力 x, 現在の y の値、そして直前の再帰ステップでの計算結果 f(x, y') を保持するために利用されます。

結論

原始帰納的関数は、計算可能性理論において非常に重要な関数のクラスであり、その定義は基本的な関数と合成、原始再帰という明確な規則に基づいています。本記事で解説したように、これらの基本的な関数はチューリングマシンによって容易に実現可能であり、また合成や原始再帰といった構成規則によって定義される関数も、より単純なチューリングマシンを組み合わせたり、繰り返し構造を模倣したりすることで、チューリングマシンによって計算可能です。

したがって、原始帰納的関数である任意の関数は、対応するチューリングマシンが存在し、その関数を計算できることが示されます。これは、原始帰納的関数がチューリング計算可能な関数のサブクラスであることを意味します。

チューリングマシンシミュレーターを活用することで、これらの抽象的な概念がテープ上の具体的な記号操作や状態遷移としてどのように実現されるかを体験的に学ぶことができます。ゼロ関数やサクセサ関数のような単純な関数から始め、徐々に複雑な構成規則を用いた関数のシミュレーションに挑戦することで、計算可能性理論の理解をさらに深めることができるでしょう。