タグシステム
タグシステム(英: Tag system)は、1943年にエミール・ポストが発表した決定性計算模型の一種であり、ポスト正準系のごく単純な形式のものである。タグシステムを抽象機械とみなした場合、ポストタグ機械(Post Tag Machine、PTM)とも呼ぶ。大まかに言えば、無限長のFIFOキューとしてのテープ装置を持った有限状態機械であり、状態遷移のたびにテープのヘッド位置から記号を読み取り、ヘッド位置から固定個の記号を消去し、最後尾に記号を追加する。
アルファベット {a1, ..., an} と、生成規則 {P1, ..., Pn} からなる m-タグシステムは、m*n 個の循環リスト (Q1, ..., Qn, -, -, ..., -) の循環タグシステムでエミュレートできる。ただし、リストの先頭 n 個以外は空文字列('-' で示している)である。Qk は Pk に対応しており、タグシステムの各記号を次のように長さ n のバイナリ文字列で置き換えることで得られる(計算にあたっては、初期単語も同様の変換が必要である)。
すなわち、ak は k 番目の位置に 1 があり、他は 0 であるようなバイナリ文字列に符号化される。従って、タグシステムにおける1行(1ステップ)は、循環タグシステムでの (m*n) 行でエミュレートされる。