タグシステム

タグシステム（）は、1943年にエミール・ポストが発表した決定性計算模型の一種であり、ポスト正準系のごく単純な形式のものである。タグシステムを抽象機械とみなした場合、ポストタグ機械（Post Tag Machine、PTM）とも呼ぶ。大まかに言えば、無限長のFIFOキューとしてのテープ装置を持った有限状態機械であり、状態遷移のたびにテープのヘッド位置から記号を読み取り、ヘッド位置から固定個の記号を消去し、最後尾に記号を追加する。
定義.
タグシステムは三つ組 （"m"、"A"、"P"）で表され、それぞれは以下の意味を持つ。
"m"-タグシステムと言った場合、"m" は削除数を指す。タグシステムの定義は書籍によって異なるが、ここでの説明は Rogozhin のものに準じている。
この定義で停止記号を使うと、計算結果として最後の単語だけを出力する。一方、停止記号を使わなければ、タグ操作の反復によって生成された単語列全体が出力となる。
典型的な別の定義として、停止記号を使わず、"m" 未満の長さの単語を全て停止単語とする定義もある。また、ポストが1943年に最初に発表した定義では、空文字列についてのみ停止するようになっていた。
例: 単純な 2-タグの例.
停止記号を使った単純な 2-タグシステムの例を以下に示す。
例: コラッツ数列の計算.
次の 2-タグシステム（停止記号を使わず、2未満の長さの単語について停止）は、"C"("n") = （"n" が偶数なら "n"/2 さもなくば (3"n"+1)/2）という形式のコラッツ関数からコラッツ数列を計算する（参考文献の De Mol 参照）。
このタグシステムでは、正の整数 "n" を "n" 個の a を繰り返した単語（aa...a）で表す。
"m"-タグシステムのチューリング完全性.
任意の "m" > 1 である "m" について、"m"-タグシステムの集合はチューリング完全である。すなわち、あるチューリング機械 T について、T をエミュレートする "m"-タグシステムが必ず存在する。特に、2-タグシステムで万能チューリング機械がエミュレート可能であることが、Wang（1963年）と Cocke & Minsky（1964年）で示されている。
逆に、あるチューリング機械でチューリング完全である "m"-タグシステムのクラスをエミュレートできることを示すことで、それが万能チューリング機械であることを示すことができる。例えば、Rogozhin（1996年）は 2-タグシステムのクラスの万能性を証明した。このときの 2-タグシステムのアルファベットは {"a"1, ..., "an", }、生成規則は {"ananW"1, ..., "ananW""n"−1, "anan", }、"Wk" は空でない単語である。そして彼は、このタグシステムのクラスを非常に小さな（4状態、6記号）のチューリング機械でシミュレートできることを示し、それが万能性を有することを証明した。
最初のタグシステムの定義.
上述の定義は、ポストが1943年に発表した当時のものとは異なる。ポストの定義では停止記号がなく、空の単語についてのみ停止するようになっていて、タグ操作 "t" は次のように定義されていた。
下線を引いた部分は、"m"-タグシステムのチューリング完全性を考慮したものである。
「タグ」の由来.
ポストの1943年の論文の脚注によると、B. P. Gill が先頭の "m" 個の記号を消さずに残していた初期のころ示唆した名称で、そのときは現在位置を示すためにテープに印を付け、ステップごとにその印が "m" 個ぶん右に移動するとしていた。このとき、印が文字列の最後尾に到達したかどうかの判定問題を "problem of tag" と名づけた。これは、いわゆる鬼ごっこ（英語で game of tag）が由来である。
循環タグシステム.
タグシステムを修正した循環タグシステム（cyclic tag system）というものがある。アルファベットは 0 と 1 のみからなり、生成規則は単語の循環リストになっていて、それを順次適用して最後の単語を適用したら、次は先頭に戻る。左端の記号が 1 であれば、そのときの生成規則に示された単語を右に追加し、0 であれば何も追加しない。どちらの場合も左端の記号を1つだけ削除する。文字列が空になるとシステムが停止する。
例.
循環タグシステムは、Matthew Cook がスティーブン・ウルフラムの下で働いていたころに考案し、Cook はこれを使ってルール110セル・オートマトンが万能性を有することを示した。その鍵となったのは、循環タグシステムがチューリング完全なタグシステムのクラスをエミュレートできるという点であった。
循環タグシステムによるタグシステムのエミュレーション.
アルファベット {"a"1, ..., "an"} と、生成規則 {"P"1, ..., "Pn"} からなる "m"-タグシステムは、"m*n" 個の循環リスト ("Q"1, ..., "Qn", -, -, ..., -) の循環タグシステムでエミュレートできる。ただし、リストの先頭 "n" 個以外は空文字列（" で示している）である。"Qk" は "Pk" に対応しており、タグシステムの各記号を次のように長さ "n" のバイナリ文字列で置き換えることで得られる（計算にあたっては、初期単語も同様の変換が必要である）。
 "a1" = 100...00
 "a2" = 010...00
 .
 "an" = 000...01
すなわち、"ak" は "k" 番目の位置に 1 があり、他は 0 であるようなバイナリ文字列に符号化される。従って、タグシステムにおける1行（1ステップ）は、循環タグシステムでの ("m*n") 行でエミュレートされる。
例.
以下に非常に小さな例を示す。
6行おき（ が付与してある）に循環タグシステムはエミュレート対象のタグシステムの計算の行に対応する符号化された内容を生成している。これが停止のエミュレートに到達するまで続く。