タグシステム
タグシステムは三つ組 (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 未満の単語である。
任意の 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記号)のチューリング機械でシミュレートできることを示し、それが万能性を有することを証明した。