タグシステム

タグシステムは、1943年にエミール・ポストが発表した決定性計算模型の一種であり、ポスト正準系のごく単純な形式のものである。タグシステムを抽象機械とみなした場合、ポストタグ機械とも呼ぶ。大まかに言えば、無限長のFIFOキューとしてのテープ装置を持った有限状態機械であり、状態遷移のたびにテープのヘッド位置から記号を読み取り、ヘッド位置から固定個の記号を消去し、最後尾に記号を追加する。

1. 定義
-----

タグシステムは三つ組 で表され、それぞれは以下の意味を持つ。

//m// - 正の整数であり、削除数と呼ぶ。
//A// - 記号群の有限アルファベット。そのうちの1つが特別な停止記号である。//A// で構成される有限の文字列を単語と呼ぶ。
//P// - 生成規則群。//A// に含まれる個々の記号 //x// に適用することを //P// で表す。停止記号への生成規則の適用は後述するように計算には何の意味もないが、利便性のため //P// = H}} とされる。//m//-タグシステムと言った場合、//m// は削除数を指す。タグシステムの定義は書籍によって異なるが、ここでの説明は Rogozhin のものに準じている。

停止単語とは、停止記号で始まる単語か、長さが //m// 未満の単語である。
変換 //t//は、停止単語以外の単語について定義されており、単語 //S// の左端の記号を //x// としたとき、//t// とは //S// の左端から //m// 個の記号を削除し、残った部分の右側に単語 //P// を追加したものである。
タグシステムにおける計算とは、変換 //t// を繰り返すことで有限単語列を生成することであり、初期状態で何らかの単語が与えられ、停止単語が生成された時点で停止する。なお、この定義では、有限回の繰り返しの間に停止単語が生成されない場合を計算とは呼べない。この定義で停止記号を使うと、計算結果として最後の単語だけを出力する。一方、停止記号を使わなければ、タグ操作の反復によって生成された単語列全体が出力となる。

典型的な別の定義として、停止記号を使わず、//m// 未満の長さの単語を全て停止単語とする定義もある。また、ポストが1943年に最初に発表した定義では、空文字列についてのみ停止するようになっていた。

1.1. 例: 単純な 2-タグの例
------------------

停止記号を使った単純な 2-タグシステムの例を以下に示す。

1.2. 例: コラッツ数列の計算
-----------------

次の 2-タグシステムは、//C// = という形式のコラッツ関数からコラッツ数列を計算する。

このタグシステムでは、正の整数 //n// を //n// 個の a を繰り返した単語で表す。

2. //m//-タグシステムのチューリング完全性
-------------------------

任意の //m// > 1 である //m// について、//m//-タグシステムの集合はチューリング完全である。すなわち、あるチューリング機械 T について、T をエミュレートする //m//-タグシステムが必ず存在する。特に、2-タグシステムで万能チューリング機械がエミュレート可能であることが、Wangと Cocke & Minskyで示されている。

逆に、あるチューリング機械でチューリング完全である //m//-タグシステムのクラスをエミュレートできることを示すことで、それが万能チューリング機械であることを示すことができる。例えば、Rogozhinは 2-タグシステムのクラスの万能性を証明した。このときの 2-タグシステムのアルファベットは H}}}、生成規則は H}}}、//Wk// は空でない単語である。そして彼は、このタグシステムのクラスを非常に小さなのチューリング機械でシミュレートできることを示し、それが万能性を有することを証明した。

3. 最初のタグシステムの定義
---------------

上述の定義は、ポストが1943年に発表した当時のものとは異なる。ポストの定義では停止記号がなく、空の単語についてのみ停止するようになっていて、タグ操作 //t// は次のように定義されていた。

空でない単語 //S// の左端の記号を //x// としたとき、//t// は最初に単語 //P// を //S// の右に追加し、次に左端から //m// 個の記号を削除する。記号数が //m// 個未満なら、全記号を削除する。下線を引いた部分は、//m//-タグシステムのチューリング完全性を考慮したものである。

3.1. 「タグ」の由来
------------

ポストの1943年の論文の脚注によると、B. P. Gill が先頭の //m// 個の記号を消さずに残していた初期のころ示唆した名称で、そのときは現在位置を示すためにテープに印を付け、ステップごとにその印が //m// 個ぶん右に移動するとしていた。このとき、印が文字列の最後尾に到達したかどうかの判定問題を "problem of tag" と名づけた。これは、いわゆる鬼ごっこが由来である。

4. 循環タグシステム
-----------

タグシステムを修正した循環タグシステムというものがある。アルファベットは 0 と 1 のみからなり、生成規則は単語の循環リストになっていて、それを順次適用して最後の単語を適用したら、次は先頭に戻る。左端の記号が 1 であれば、そのときの生成規則に示された単語を右に追加し、0 であれば何も追加しない。どちらの場合も左端の記号を1つだけ削除する。文字列が空になるとシステムが停止する。

4.1. 例
------

循環タグシステムは、Matthew Cook がスティーブン・ウルフラムの下で働いていたころに考案し、Cook はこれを使ってルール110セル・オートマトンが万能性を有することを示した。その鍵となったのは、循環タグシステムがチューリング完全なタグシステムのクラスをエミュレートできるという点であった。

5. 循環タグシステムによるタグシステムのエミュレーション
-----------------------------

アルファベット {//a//1, ..., //an//} と、生成規則 {//P//1, ..., //Pn//} からなる //m//-タグシステムは、//m*n// 個の循環リスト  の循環タグシステムでエミュレートできる。ただし、リストの先頭 //n// 個以外は空文字列である。//Qk// は //Pk// に対応しており、タグシステムの各記号を次のように長さ //n// のバイナリ文字列で置き換えることで得られる。

//a1// = 100...00//a2// = 010...00 . . .//an// = 000...01

すなわち、//ak// は //k// 番目の位置に 1 があり、他は 0 であるようなバイナリ文字列に符号化される。従って、タグシステムにおける1行は、循環タグシステムでの  行でエミュレートされる。

5.1. 例
------

以下に非常に小さな例を示す。 6行おきに循環タグシステムはエミュレート対象のタグシステムの計算の行に対応する符号化された内容を生成している。これが停止のエミュレートに到達するまで続く。

6. 参考文献
-------

Cocke, J., and Minsky, M.: "Universality of Tag Systems with P=2", //J. Assoc. Comput. Mach.// 11, 15-20, 1964.
De Mol, L.: [1], Preprint , to appear in //Theoretical Computer Science//.
Marvin Minsky 1961, //Recursive Unsolvability of Post's Problem of "Tag" and other Topics in Theory of Turing Machines", //the Annals of Mathematics, 2nd ser., Vol. 74, No. 3. , pp. 437-455. Stable URL: http://links.jstor.org/sici?sici=0003-486X%2819611%292%3A74%3A3%3C437%3ARUOPPO%3E2.0.CO%3B2-N.
Marvin Minsky, 1967, //Computation: Finite and Infinite Machines//, Prentice-Hall, Inc. Englewoord Cliffs, N.J., no ISBN, Library of Congress Card Catalog number 67-12342.
Post, E.: "Formal reductions of the combinatorial decision problem", //American Journal of Mathematics//, 65 , 197-215 . 
Rogozhin, Yu.: "Small Universal Turing Machines", //Theoret. Comput. Sci.// 168, 215-240, 1996.
Uspensky, V.A.: "A Post Machine" , Moscow, "Nauka", 1979.
Wang, H.: "Tag Systems and Lag Systems", //Math. Annalen// 152, 65-74, 1963.

7. 外部リンク
--------

[2] Wolfram MathWorld
[3] Wolfram MathWorld
[4] フリーソフトウェア
[5] 循環タグシステムの変種