タグシステム
From Wikipedia, the free encyclopedia
例: 単純な 2-タグの例
タグシステムは三つ組 （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-タグシステム
アルファベット: {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-タグシステムのアルファベットは {a1, ..., an, H}、生成規則は {ananW1, ..., ananWn−1, anan, H}、Wk は空でない単語である。そして彼は、このタグシステムのクラスを非常に小さな（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セル・オートマトンが万能性を有することを示した。その鍵となったのは、循環タグシステムがチューリング完全なタグシステムのクラスをエミュレートできるという点であった。