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

チューリングマシンによる単項表現インクリメント:シミュレーターで追う動作例

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

チューリングマシンは、計算の基本モデルとして計算機科学において非常に重要な概念です。抽象的な定義だけではなく、具体的な問題を解くチューリングマシンの動作を追うことは、その理論への理解を深める上で有効です。本記事では、単項表現された自然数をインクリメント(1増やす)するチューリングマシンを例に、その動作をシミュレーターでのステップと対応させて解説します。

単項表現とは

自然数を表現する方法の一つに、単項表現(Unary Representation)があります。これは、数 $n$ を、特定の記号(例えば 1)を $n$ 個並べることで表現する方法です。例えば、記号 1 を使用する場合、

のように表されます。本記事では、記号 1 を使用し、テープ上の空白記号を _ とします。入力は _111_ のように、単項表現された数の両端が空白で囲まれている状態を想定します。

インクリメントのアルゴリズム

単項表現された数 $n$ をインクリメントして $n+1$ にするためには、表現の末尾に記号 1 を一つ追加すれば良いだけです。例えば、111 (数 3) を 1111 (数 4) にするには、末尾に 1 を追加します。

チューリングマシンがこの操作を行う手順は以下のようになります。

  1. テープ上の単項表現された数の右端、つまり最初の空白記号の位置を見つけます。
  2. その空白記号を記号 1 に書き換えます。
  3. 停止します。

この単純なアルゴリズムをチューリングマシンの遷移として定義してみましょう。

チューリングマシンの設計

このチューリングマシンは、以下の要素で構成されます。

遷移関数 $\delta$ は以下のようになります。

  1. $(q_{start}, _) \to (q_{find_blank}, _, Right)$
    • 開始状態では、最初にある可能性のある左端の空白を無視して右へ移動し、単項表現の本体を見つけに行きます。状態を q_find_blank にします。
  2. $(q_{find_blank}, 1) \to (q_{find_blank}, 1, Right)$
    • q_find_blank 状態では、1 を読み取ったらそのまま右へ移動し、単項表現の末尾(つまり次の空白記号)を探し続けます。
  3. $(q_{find_blank}, _) \to (q_{write_one}, 1, Right)$
    • q_find_blank 状態で空白記号 _ を読み取ったら、それは単項表現の右端の空白です。状態を q_write_one に遷移させます。この空白記号の次のセル1 を書き込みたいので、ヘッドをまず右に移動させます。(この設計の場合、空白を読み取ったセルに 1 を書き換え、右に移動してから停止する方が一般的かもしれません。ここでは、アルゴリズム通り「末尾の空白の1 を書く」という解釈で設計を進めます。ただし、一般的なチューリングマシンの定義では、読み取ったセルに書き込み、移動するという順序なので、(q_find_blank, '_') \to (q_write_one, '1', Stay) として、q_write_one で移動し停止、または(q_find_blank, '_') \to (q_halt, '1', Stay) のように読み取った空白を 1 に書き換えて停止、の方が標準的です。ここでは、アルゴリズムの「末尾に追加」を表現するため、空白の「右」に書く設計を試みます。より一般的な設計としては、空白を読み取ったらそのセルに 1 を書き込み、停止するのが適切です。一般的な設計に従い修正します。)

修正後のより一般的な遷移関数 $\delta$:

この修正後の設計は、単項表現の末尾(右端の 1 の直後の空白)を 1 に書き換えることで、インクリメントを実現します。

シミュレーターでの動作例

初期テープの状態を _ _ 1 1 1 _ _ (数 3 を表現)とします。ヘッドは一番左のセルにあると仮定します。

| ステップ | 現在の状態 | 読み取った記号 | 書き込む記号 | 移動方向 | 次の状態 | テープの状態(ヘッド位置) | 解説 | | :------- | :--------- | :------------- | :----------- | :------- | :--------- | :------------------------- | :---------------------------------------- | | 0 | $q_{start}$| _ | _ | Right | $q_{find_blank}$ | __1 1 1 _ _ | 左端の空白をスキップ、右へ移動。 | | 1 | $q_{find_blank}$ | _ | _ | Right | $q_{find_blank}$ | _ _11 1 _ _ | 次の空白もスキップ、右へ移動。(修正:これはテープ本体が始まってない状態。q_startで最初の1か空白まで行くべき) |

さらに修正した開始状態からの遷移: $q_{start}$ からは、最初の 1 または最初の右端の空白まで移動することにします。

修正後の遷移関数 $\delta$:

シミュレーターでの動作例(初期テープ _ 1 1 1 _ 数 3):

| ステップ | 現在の状態 | 読み取った記号 | 書き込む記号 | 移動方向 | 次の状態 | テープの状態(ヘッド位置) | 解説 | | :------- | :--------- | :------------- | :----------- | :------- | :--------- | :------------------------- | :------------------------------------- | | 0 | $q_{start}$| _ | _ | Right | $q_{start}$| _1 1 1 _ | 左端の空白をスキップ、右へ移動。 | | 1 | $q_{start}$| 1 | 1 | Right | $q_{find_blank}$ | _ 11 1 _ | 最初の 1 を読み取り、右へ移動し状態変更。| | 2 | $q_{find_blank}$ | 1 | 1 | Right | $q_{find_blank}$ | _ 1 11 _ | 1 を読み取り、右へ移動。 | | 3 | $q_{find_blank}$ | 1 | 1 | Right | $q_{find_blank}$ | _ 1 1 1_ | 1 を読み取り、右へ移動。 | | 4 | $q_{find_blank}$ | _ | 1 | Stay | $q_{halt}$ | _ 1 1 11 | 右端の空白を 1 に書き換え、停止。 |

結果テープは _ 1 1 1 1 となり、数 4 を正しく表現できています。

シミュレーターでの動作例(初期テープ _ _ 数 0):

| ステップ | 現在の状態 | 読み取った記号 | 書き込む記号 | 移動方向 | 次の状態 | テープの状態(ヘッド位置) | 解説 | | :------- | :--------- | :------------- | :----------- | :------- | :--------- | :------------------------- | :------------------------------------- | | 0 | $q_{start}$| _ | _ | Right | $q_{start}$| __ | 左端の空白をスキップ、右へ移動。 | | 1 | $q_{start}$| _ | 1 | Stay | $q_{halt}$ | _1_ | 右端(かつ最初に見つけた)空白を 1 に書き換え、停止。|

結果テープは _ 1 _ となり、数 1 を正しく表現できています。

理論とシミュレーターの対応

上記ステップ表は、チューリングマシンの理論的な遷移関数 $\delta(q, a) = (q', b, d)$ が、シミュレーター上で具体的にどのようにテープの状態、ヘッド位置、現在の状態を変化させるかを示しています。

このように、シミュレーターを用いることで、抽象的な遷移関数の定義が、テープ上での具体的な記号の操作やヘッドの動きといった物理的な(仮想的な)動作として視覚化され、チューリングマシンの計算プロセスへの理解を深めることができます。

まとめ

本記事では、単項表現された自然数をインクリメントするというシンプルな計算問題を例に、チューリングマシンの設計とそのシミュレーター上での具体的な動作ステップを追いました。右端の空白を見つけて 1 に書き換えるという基本的な操作の組み合わせによって、この計算が実現できることを確認しました。

計算機科学における多くの計算可能な関数は、このようなチューリングマシンの基本的な操作の組み合わせによって実現できます。ぜひシミュレーターを活用して、本記事で紹介したインクリメントマシンを実際に構築・実行し、その動作を観察してみてください。他の様々な計算問題についても、どのようにチューリングマシンで表現できるかを考えてみると良いでしょう。