タグシステム

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

例: 単純な 2-タグの例

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

2-タグシステム 
    アルファベット: {a,b,c,H} 
    生成規則:
         a  -->  ccbaH
         b  -->  cca
         c  -->  cc

計算例    初期単語:  baa
                 acca
                   caccbaH
                     ccbaHcc
                       baHcccc
                         Hcccccca （停止）

例: コラッツ数列の計算

次の 2-タグシステム（停止記号を使わず、2未満の長さの単語について停止）は、C(n) = （n が偶数なら n/2 さもなくば (3n+1)/2）という形式のコラッツ関数からコラッツ数列を計算する（参考文献の De Mol 参照）。
このタグシステムでは、正の整数 n を n 個の a を繰り返した単語（aa...a）で表す。

2-タグシステム 
    アルファベット: {a,b,c} 
    生成規則:
         a  -->  bc
         b  -->  a
         c  -->  aaa

計算例        初期単語:   aaa <--> n=3
                      abc  
                        cbc
                          caaa
                            aaaaa  <--> 5
                              aaabc
                                abcbc
                                  cbcbc
                                    cbcaaa
                                      caaaaaa
                                        aaaaaaaa  <--> 8
                                          aaaaaabc
                                            aaaabcbc
                                              aabcbcbc
                                                bcbcbcbc
                                                  bcbcbca
                                                    bcbcaa
                                                      bcaaa
                                                        aaaa  <--> 4
                                                          aabc
                                                            bcbc
                                                              bca
                                                                aa  <--> 2
                                                                  bc
                                                                    a  <--> 1
                                                                   （停止）

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

任意の m > 1 である m について、m-タグシステムの集合はチューリング完全である。すなわち、あるチューリング機械 T について、T をシミュレートする m-タグシステムが必ず存在する。特に、2-タグシステムで万能チューリング機械のシミュレートが可能であることが、Wang（1963年）と Cocke & Minsky（1964年）で示されている。
逆に、あるチューリング機械でチューリング完全である m-タグシステムのクラスをシミュレートできることを示すことで、それが万能チューリング機械であることを示すことができる。例えば、Rogozhin（1996年）は 2-タグシステムのクラスの万能性を証明した。このときの 2-タグシステムのアルファベットは {a₁, ..., aₙ, H}、生成規則は {aₙaₙW₁, ..., aₙaₙWₙ−1, aₙaₙ, H}、Wₖ は空でない単語である。そして彼は、このタグシステムのクラスを非常に小さな（4状態、6記号）のチューリング機械でシミュレートできることを示し、それが万能性を有することを証明した。

「タグ」の由来

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

循環タグシステム

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

例

循環タグシステム 生成規則: (010, 000, 1111)

計算例 初期単語: 11001
     生成規則            単語
    ----------         --------------
       010             11001
       000              1001010
       1111              001010000
       010                01010000
       000                 1010000
       1111                 010000000
       010                   10000000
        .                      .
        .                      .
循環タグシステムは、Matthew Cook がスティーブン・ウルフラムの下で働いていたころに考案し、Cook はこれを使ってルール110セル・オートマトンが万能性を有することを示した。その鍵となったのは、循環タグシステムがチューリング完全なタグシステムのクラスをエミュレートできるという点であった。

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

アルファベット {a₁, ..., aₙ} と、生成規則 {P₁, ..., Pₙ} からなる m-タグシステムは、m*n 個の循環リスト (Q₁, ..., Qₙ, -, -, ..., -) の循環タグシステムでエミュレートできる。ただし、リストの先頭 n 個以外は空文字列（'-' で示している）である。Qₖ は Pₖ に対応しており、タグシステムの各記号を次のように長さ n のバイナリ文字列で置き換えることで得られる（計算にあたっては、初期単語も同様の変換が必要である）。
a₁ = 100...00
a₂ = 010...00
.
.
.
aₙ = 000...01
すなわち、aₖ は k 番目の位置に 1 があり、他は 0 であるようなバイナリ文字列に符号化される。従って、タグシステムにおける1行（1ステップ）は、循環タグシステムでの (m*n) 行でエミュレートされる。

例

以下に非常に小さな例を示す。

2-タグシステム    生成規則: (a --> bb, b --> abH, H --> H)
    アルファベット符号化: a = 100, b = 010, H = 001 
    生成規則の符号化: (bb = 010 010, abH = 100 010 001, H = 001)

循環タグシステム 
    生成循環リスト: (010 010, 100 010 001, 001, -, -, -)

タグシステムでの計算    初期単語:      ba
                    abH
                      Hbb (halt)

循環タグシステムでの計算    初期単語: 010 100 (=ba)

     生成規則          単語
    ----------       -------------------------------
  * 010 010          010 100  (=ba)
    100 010 001       10 100
    001                0 100 100 010 001
    -                    100 100 010 001
    -                     00 100 010 001
    -                      0 100 010 001
  * 010 010                  100 010 001  (=abH)
    100 010 001               00 010 001 010 010
    001                        0 010 001 010 010
    -                            010 001 010 010
    -                             10 001 010 010
    -                              0 001 010 010
  * 010 010                          001 010 010  (=Hbb) 停止のエミュレート    100 010 001                       01 010 010
    001                                1 010 010
    -                                    010 010 001
    ...                                    ...
6行おき（'*' が付与してある）に循環タグシステムはエミュレート対象のタグシステムの計算の行に対応する符号化された内容を生成している。これが停止のエミュレートに到達するまで続く。