はじめに
Rogozhinさんは、この論文にて、2-タグシステムをシミュレートできる状態数が2つ、使用する記号が18つのチューリングマシンの構成法を示しました。この記事では、論文をもとにして実際に構成を行う例を示します。
チューリング完全な2-タグシステムをこのようにシミュレートできる、チューリングマシンもまた、チューリング完全です。
構成法
今回は、 次の2-タグシステムをチューリングマシンでシミュレートすることを考えます。
- 使用される文字の集合： $[A, B, H]$
- 生成規則：
- $A \rightarrow BH$
- $B \rightarrow A$
- $H \rightarrow \mathbf{STOP}$
- 与える初期語： $ABB$
こうしたとき、語は次のように処理されるはずです：
$ABB \rightarrow BBH \rightarrow HA$
1. 文字に番号を振る
タグシステムの各文字に整数の番号を振ります。
| 番号 | 文字 | 対応する生成規則の出力 |
|---|---|---|
| 1 | $A$ | $BH$ |
| 2 | $B$ | $A$ |
| 3 | $H$ | $\mathbf{STOP}$ |
2. 文字を表す記号列を決定する
タグシステムの文字は、記号列 $1^{N_i}$ (記号$1$を$N_i$回繰り返したもの)で表されます。ここで、$N_i$は次のように再帰的に定義されます：
\begin{eqnarray}
N_1&=&1 \\
N_{i+1}&=&N_i + m_i + 1
\end{eqnarray}
$i$はその文字に割り振った整数、$m_i$は$i$番目の生成規則の出力の文字数です。
これを各文字について求めます。
| 番号 | 文字 | 対応する生成規則の出力 | $N_i$ | この文字を表す記号列 |
|---|---|---|---|---|
| 1 | $A$ | $BH$ | 1 | 1 |
| 2 | $B$ | $A$ | 1 + 2 + 1 = 4 | $1^4$ |
| 3 | $H$ | $\mathbf{STOP}$ | 4 + 1 + 1 = 6 | $1^6$ |
3. 生成規則を表す記号列を決定する
$i$ 番目の生成規則( $P_i$ )は、それを構成する文字の表現の逆順を $1b$ で区切りながら以下のように記述します。
P_i = bb111...11\ 1b\ 111...11\ 1b\ 111...11
ただし、STOPの場合は、$\overleftarrow{c_1} \overleftarrow{c_1}$ で表されます。
| 番号 | 文字 | 対応する生成規則の出力 | この文字を表す記号列 | この生成規則を表す記号列 |
|---|---|---|---|---|
| 1 | $A$ | $BH$ | 1 | $bb(1^6)1b(1^4)$ |
| 2 | $B$ | $A$ | $1^4$ | $bb1$ |
| 3 | $H$ | $\mathbf{STOP}$ | $1^6$ | $\overleftarrow{c_1} \overleftarrow{c_1}$ |
4. 初期語を表す記号列を決定する
初期語($S$)は、それを構成する文字の表現を記号 $c$ で区切りながら以下のように記述します。
S = 111...11c111...11c111...11c
今回入力する初期語は$ABB$なので、これは
1c(1^4)c(1^4)c
と表されます。
5. 部品を連結して完成
3と4で求めた記号列を以下のように組み合わせ、これを初期テープとして完成です。
... \overleftarrow{1}\overleftarrow{1}P_{i+1}P_{i}...P_1b\underline{b}S\overleftarrow{1}\overleftarrow{1} ...
(テープの長さは無限なので、両端の$\overleftarrow{1}$は無限に続きます。)
求めたやつを組み合わせると：
| 番号 | 文字 | 対応する生成規則の出力 | この文字を表す記号列 | この生成規則を表す記号列 |
|---|---|---|---|---|
| 1 | $A$ | $BH$ | 1 | $bb(1^6)1b(1^4)$ |
| 2 | $B$ | $A$ | $1^4$ | $bb1$ |
| 3 | $H$ | $\mathbf{STOP}$ | $1^6$ | $\overleftarrow{c_1} \overleftarrow{c_1}$ |
より、今回はテープは次のように初期化されます。
...\overleftarrow{1}\overleftarrow{1}\overleftarrow{c_1} \overleftarrow{c_1}bb1bb(1^6)1b(1^4)b\underline{b}1c(1^4)c(1^4)c\overleftarrow{1}\overleftarrow{1}...
チューリングマシンの残りの構成要素は、次の様です。
- マシンの内部状態：$q_1, q_2$
- マシンのヘッドの初期位置：下線を引いたところ。 (どのタグシステムでも同じ。)
- マシンのプログラム(元論文よりコピー。どのタグシステムでも同じ。)
- 受理状態：なし ($q_1, \overleftarrow{c_1}$に対応するプログラムによってのみ停止する。)
これで、タグシステムをシミュレートする、チューリングマシンが完成しました。
出来たチューリングマシンを実際に動かしてみる
さて、せっかく作ったなら動かして動作確認したいので、作ったチューリングマシンを動かすことにします。(手元で作った雑プログラムでシミュレーションをしました。)
先ほど完成したテープを使ってチューリングマシンを動かすと、結果として
...\overleftarrow{1}\overleftarrow{c_1}c_2\overrightarrow{b}\overrightarrow{b}\overrightarrow{1}\overrightarrow{b}\overrightarrow{b}(\overrightarrow{1}^6)\overrightarrow{1}\overrightarrow{b}(\overrightarrow{1}^4)\overrightarrow{b}\overrightarrow{b}\overrightarrow{1}\overrightarrow{1}\overrightarrow{1}\overrightarrow{1}\overrightarrow{1}\overrightarrow{1}\overrightarrow{1}\overrightarrow{1}\overrightarrow{1}\overrightarrow{1}\overrightarrow{1}\overrightarrow{1}\overrightarrow{1}\overrightarrow{1}\overrightarrow{1}\overrightarrow{1}\overrightarrow{1}\overrightarrow{1}\overrightarrow{1}\overrightarrow{1}\overrightarrow{1}\overrightarrow{1}\overrightarrow{1}\overrightarrow{1}1c\overleftarrow{1}...
を得ます。色々印がついていて分かりづらいですが、最後に$1c$が残っています。これは、処理した結果、最後に$HA$ という語が残った...として解釈することができます。($H$は処理の都合上消えていますが、処理が停止したということは$H$を読み込んだことを示していますから、結局$HA$であることが分かるのです。)これによって、本当にタグシステムをシミュレーションできることが分かりました。
参考までに、「実行の途中で現れる、語 BBH を表すテープ」も付記しておきます。
...\overleftarrow{1}\overleftarrow{c_1}\overleftarrow{c_1}bb1bb1111111b1111b\overleftarrow{b}c_2c_2c_2c_2c_2c_2c_21111c1111c111111c\overleftarrow{1}...
(後半の、$1111c1111c111111c$の部分が、$BBH$を表しています。)
終わりに
2-タグシステムは、チューリング完全である系を擁しています。
Rogozhinさんは、このように任意の2-タグシステムをシミュレートできるチューリングマシンを示すことで、そのチューリングマシンも同じくチューリング完全であることを示しました。
この様にしてできた2状態18記号の万能チューリングマシンは、「Magic:the Gathering」がチューリング完全であることの証明にも用いられています。
補足1: 2-タグシステムとは？
語 (文字の並び) を受け取って、以下の処理を「先頭が終了文字になるまで」繰り返すシステムです。
- 先頭文字を確認し、対応する文字列を末尾に追加する。
- 最初の2文字を削除する。
例
構成の説明に使った次のようなタグシステムの実行を考えます。
- 使用される文字の集合： $[A, B, H]$
- 生成規則：
- $A \rightarrow BH$
- $B \rightarrow A$
- $H \rightarrow \mathbf{STOP}$
このタグシステムに$ABB$を与えると、語は次のように処理されるはずです：
\underline{AB}B \rightarrow B\underline{BH} \quad\text{(先頭が$A$なので末尾に$BH$を追加し、先頭の二文字($AB$)を削除する。)} \\
\underline{BB}H \rightarrow H\underline{A} \quad\text{(先頭が$B$なので末尾に$A$を追加し、先頭の二文字($BB$)を削除する。)}
2-タグシステムは、チューリング完全な系を擁することが知られています。
補足2: チューリングマシンとは？
記号列(テープ)を受け取って、次のような処理を繰り返すシステムです。
通常、受理状態であるか動作が定義されていないかのどちらかが終了条件ですが、今回は動作を停止させる(HALT)命令を考えることでこれを終了条件としています。
- テープの特定の位置を読み込む。
- 読み込んだ記号と現在の状態によって、① 状態を変化させ、②テープの読んだ位置に特定の記号を書き込み、③次に読む位置を左右のどちらかに移動する。
(「読み書きする位置」を、「ヘッドの位置」と言います。)
例
次のようなごくごく簡単なチューリングマシンを考えます。
- 使用する状態： $q_1, q_2$
- 初期状態： $q_1$
- 使用する記号： $[A, B, S]$
- 空白記号： $S$ (テープは両端とも、この記号が無限に続きますが、簡略化のため今回は省略します。)
- 動作規則
- $q_1, A \rightarrow q_1, B, \text{right}$
- $q_1, B \rightarrow q_2, A, \text{left}$
- $q_2, B \rightarrow \text{HALT}$
このマシンに記号列$\underline{A}B$ を与える(下線部が最初のヘッドの位置)と、次のように動作するはずです。
q_1, \underline{A}B \rightarrow q_1, B\underline{B} \quad\text{(状態$q_1$の時に$A$を読み込んだので、$B$を書き込み、状態は$q_1$のままで、ヘッドの位置を右に移動させる。)} \\
q_1, B\underline{B} \rightarrow q_2, \underline{B}A
\quad\text{(状態$q_1$の時に$B$を読み込んだので、$A$を書き込み、状態を$q_2$に変化させ、ヘッドの位置を左に移動させる。)} \\
q_2, \underline{B}A \rightarrow \text{HALT}
\quad\text{(状態$q_2$の時に$B$を読み込んだので、処理を終了する。)}
チューリング完全とは？
まず、万能チューリングマシンとは、「渡すテープを付け替えるだけで、任意のチューリングマシンをシミュレーションできる」チューリングマシンです。
チューリング完全とは、万能チューリングマシンが持つ計算能力と等しい計算能力を持っているという事です。
平たく言えば、入力を付け替えるだけで任意のチューリングマシンをシミュレーションできる計算系は、チューリング完全です。
万能チューリングマシン、チューリング完全については、この記事 が分かりやすいです。