チューリングマシンによる単項表現インクリメント：シミュレーターで追う動作例
チューリングマシンは、計算の基本モデルとして計算機科学において非常に重要な概念です。抽象的な定義だけではなく、具体的な問題を解くチューリングマシンの動作を追うことは、その理論への理解を深める上で有効です。本記事では、単項表現された自然数をインクリメント（1増やす）するチューリングマシンを例に、その動作をシミュレーターでのステップと対応させて解説します。
単項表現とは
自然数を表現する方法の一つに、単項表現（Unary Representation）があります。これは、数 $n$ を、特定の記号（例えば 1）を $n$ 個並べることで表現する方法です。例えば、記号 1 を使用する場合、
- 0 は空文字列 $\epsilon$
- 1 は
1 - 2 は
11 - 3 は
111
のように表されます。本記事では、記号 1 を使用し、テープ上の空白記号を _ とします。入力は _111_ のように、単項表現された数の両端が空白で囲まれている状態を想定します。
インクリメントのアルゴリズム
単項表現された数 $n$ をインクリメントして $n+1$ にするためには、表現の末尾に記号 1 を一つ追加すれば良いだけです。例えば、111 (数 3) を 1111 (数 4) にするには、末尾に 1 を追加します。
チューリングマシンがこの操作を行う手順は以下のようになります。
- テープ上の単項表現された数の右端、つまり最初の空白記号の位置を見つけます。
- その空白記号を記号
1に書き換えます。 - 停止します。
この単純なアルゴリズムをチューリングマシンの遷移として定義してみましょう。
チューリングマシンの設計
このチューリングマシンは、以下の要素で構成されます。
- 状態集合 $Q$: ${q_{start}, q_{find_blank}, q_{write_one}, q_{halt}}$
- $q_{start}$: 開始状態
- $q_{find_blank}$: 右端の空白記号を探す状態
- $q_{write_one}$: 空白記号を見つけて
1を書き込む状態 - $q_{halt}$: 停止状態
- 入力アルファベット $\Sigma$: ${
1}$ - テープアルファベット $\Gamma$: ${
1,_}$ (入力アルファベットと空白記号を含む) - 開始状態 $q_0$: $q_{start}$
- 空白記号 $B$:
_ - 停止状態集合 $F$: ${q_{halt}}$
- 遷移関数 $\delta$: $(現在の状態, 読み取った記号) \to (次の状態, 書き込む記号, ヘッドの移動方向)$
遷移関数 $\delta$ は以下のようになります。
- $(q_{start},
_) \to (q_{find_blank},_, Right)$- 開始状態では、最初にある可能性のある左端の空白を無視して右へ移動し、単項表現の本体を見つけに行きます。状態を
q_find_blankにします。
- 開始状態では、最初にある可能性のある左端の空白を無視して右へ移動し、単項表現の本体を見つけに行きます。状態を
- $(q_{find_blank},
1) \to (q_{find_blank},1, Right)$q_find_blank状態では、1を読み取ったらそのまま右へ移動し、単項表現の末尾（つまり次の空白記号）を探し続けます。
- $(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$:
- $(q_{start},
_) \to (q_{find_blank},_, Right)$- 左端の空白をスキップして右へ移動します。
- $(q_{start},
1) \to (q_{find_blank},1, Right)$- 左端に空白がない場合も、そのまま右へ移動します。
- $(q_{find_blank},
1) \to (q_{find_blank},1, Right)$- 単項表現の本体を読み取ったら、右へ移動し続けます。
- $(q_{find_blank},
_) \to (q_{halt},1, Stay)$- 右端の空白記号
_を読み取ったら、そのセルに1を書き込み、停止します。
- 右端の空白記号
この修正後の設計は、単項表現の末尾（右端の 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 または最初の右端の空白まで移動することにします。
- $(q_{start},
_) \to (q_{start},_, Right)$- 左端の空白をスキップして右へ移動します。
- $(q_{start},
1) \to (q_{find_blank},1, Right)$- 最初の
1を見つけたら、それをスキップして右へ移動し、q_find_blank状態に入ります。
- 最初の
- $(q_{start},
B) \to (q_{halt},1, Stay)$ (Bは空白記号)- テープが空(
__...__)の場合（数0）、最初の空白を1に書き換え、数1にします。
- テープが空(
修正後の遷移関数 $\delta$:
- $(q_{start},
_) \to (q_{start},_, Right)$ - $(q_{start},
1) \to (q_{find_blank},1, Right)$ - $(q_{find_blank},
1) \to (q_{find_blank},1, Right)$ - $(q_{find_blank},
_) \to (q_{halt},1, Stay)$
シミュレーターでの動作例（初期テープ _ 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)$ が、シミュレーター上で具体的にどのようにテープの状態、ヘッド位置、現在の状態を変化させるかを示しています。
- 現在の状態と読み取った記号: シミュレーターの現在のステップにおけるマシン内部の状態と、ヘッドが位置するテープセルから読み取った記号が、遷移関数の入力 $(q, a)$ に対応します。
- 書き込む記号と移動方向: 遷移関数が出力する $b$ と $d$ は、シミュレーターがテープ上の現在のセルに書き込む記号と、ヘッドを次に移動させる方向に対応します。
- 次の状態: 遷移関数が出力する $q'$ は、シミュレーターがヘッド移動後に遷移する新しい状態に対応します。
- テープの状態変化とヘッド位置: シミュレーター上では、書き込み記号がテープに反映され、ヘッド位置が指示された方向に移動することで、視覚的に動作を追うことができます。
このように、シミュレーターを用いることで、抽象的な遷移関数の定義が、テープ上での具体的な記号の操作やヘッドの動きといった物理的な（仮想的な）動作として視覚化され、チューリングマシンの計算プロセスへの理解を深めることができます。
まとめ
本記事では、単項表現された自然数をインクリメントするというシンプルな計算問題を例に、チューリングマシンの設計とそのシミュレーター上での具体的な動作ステップを追いました。右端の空白を見つけて 1 に書き換えるという基本的な操作の組み合わせによって、この計算が実現できることを確認しました。
計算機科学における多くの計算可能な関数は、このようなチューリングマシンの基本的な操作の組み合わせによって実現できます。ぜひシミュレーターを活用して、本記事で紹介したインクリメントマシンを実際に構築・実行し、その動作を観察してみてください。他の様々な計算問題についても、どのようにチューリングマシンで表現できるかを考えてみると良いでしょう。