タグシステム

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

定義

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

m - 正の整数であり、削除数（deletion number）と呼ぶ。
A - 記号群の有限アルファベット。そのうちの1つが特別な停止記号（halting symbol）である。A で構成される（空も含む）有限の文字列を単語（words）と呼ぶ。
P - 生成規則群。A に含まれる個々の記号 x に適用することを P(x) で表す（生成するとも呼ぶ）。停止記号への生成規則の適用（P(H)）は後述するように計算には何の意味もないが、利便性のため P(H) = H とされる。

m-タグシステムと言った場合、m は削除数を指す。タグシステムの定義は書籍によって異なるが、ここでの説明は Rogozhin のものに準じている。

停止単語（halting word）とは、停止記号で始まる単語か、長さが m 未満の単語である。
変換 t（タグ操作とも）は、停止単語以外の単語について定義されており、単語 S の左端の記号を x としたとき、t(S) とは S の左端から m 個の記号を削除し、残った部分の右側に単語 P(x) を追加したものである。
タグシステムにおける計算とは、変換 t を繰り返すことで有限単語列を生成することであり、初期状態で何らかの単語が与えられ、停止単語が生成された時点で停止する。なお、この定義では、有限回の繰り返しの間に停止単語が生成されない場合を計算とは呼べない。

この定義で停止記号を使うと、計算結果として最後の単語だけを出力する。一方、停止記号を使わなければ、タグ操作の反復によって生成された単語列全体が出力となる。

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

例: 単純な 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_n, H}、生成規則は {a_na_nW₁, ..., a_na_nW_n−1, a_na_n, H}、W_k は空でない単語である。そして彼は、このタグシステムのクラスを非常に小さな（4状態、6記号）のチューリング機械でシミュレートできることを示し、それが万能性を有することを証明した。

最初のタグシステムの定義

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

空でない単語 S の左端の記号を x としたとき、t(S) は最初に単語 P(x) を S の右に追加し、次に左端から m 個の記号を削除する。記号数が m 個未満なら、全記号を削除する。

下線を引いた部分は、m-タグシステムのチューリング完全性を考慮したものである。

「タグ」の由来

ポストの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_n} と、生成規則 {P₁, ..., P_n} からなる m-タグシステムは、m*n 個の循環リスト (Q₁, ..., Q_n, -, -, ..., -) の循環タグシステムでエミュレートできる。ただし、リストの先頭 n 個以外は空文字列（'-' で示している）である。Q_k は P_k に対応しており、タグシステムの各記号を次のように長さ n のバイナリ文字列で置き換えることで得られる（計算にあたっては、初期単語も同様の変換が必要である）。

a₁ = 100...00
a₂ = 010...00
.
.
.
a_n = 000...01

すなわち、a_k は 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行おき（'*' が付与してある）に循環タグシステムはエミュレート対象のタグシステムの計算の行に対応する符号化された内容を生成している。これが停止のエミュレートに到達するまで続く。

参考文献

Cocke, J., and Minsky, M.: "Universality of Tag Systems with P=2", J. Assoc. Comput. Mach. 11, 15-20, 1964.
De Mol, L.: "Tag systems and Collatz-like functions", Preprint (Nr. 314), 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. (Nov., 1961), 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 (2), 197-215 (1943). (Tag systems are introduced on p.203ff.)
Rogozhin, Yu.: "Small Universal Turing Machines", Theoret. Comput. Sci. 168, 215-240, 1996.
Uspensky, V.A.: "A Post Machine" (in Russian), Moscow, "Nauka", 1979.
Wang, H.: "Tag Systems and Lag Systems", Math. Annalen 152, 65-74, 1963.

外部リンク

Tag System Wolfram MathWorld
Cyclic Tag System Wolfram MathWorld
C++ Simulator of a Nondeterministic and Deterministic Multitape Post Machine フリーソフトウェア
Bitwise Cyclic Tag (BCT) 循環タグシステムの変種