タグシステム（）は、1943年にエミール・ポストが発表した決定性計算模型の一種であり、ポスト正準系のごく単純な形式のものである。タグシステムを抽象機械とみなした場合、ポストタグ機械（Post Tag Machine、PTM）とも呼ぶ。大まかに言えば、無限長のFIFOキューとしてのテープ装置を持った有限状態機械であり、状態遷移のたびにテープのヘッド位置から記号を読み取り、ヘッド位置から固定個の記号を消去し、最後尾に記号を追加する。タグシステムは三つ組 （"m"、"A"、"P"）で表され、それぞれは以下の意味を持つ。"m"-タグシステムと言った場合、"m" は削除数を指す。タグシステムの定義は書籍によって異なるが、ここでの説明は Rogozhin のものに準じている。この定義で停止記号を使うと、計算結果として最後の単語だけを出力する。一方、停止記号を使わなければ、タグ操作の反復によって生成された単語列全体が出力となる。典型的な別の定義として、停止記号を使わず、"m" 未満の長さの単語を全て停止単語とする定義もある。また、ポストが1943年に最初に発表した定義では、空文字列についてのみ停止するようになっていた。停止記号を使った単純な 2-タグシステムの例を以下に示す。次の 2-タグシステム（停止記号を使わず、2未満の長さの単語について停止）は、"C"("n") = （"n" が偶数なら "n"/2 さもなくば (3"n"+1)/2）という形式のコラッツ関数からコラッツ数列を計算する（参考文献の De Mol 参照）。このタグシステムでは、正の整数 "n" を "n" 個の a を繰り返した単語（aa...a）で表す。任意の "m" > 1 である "m" について、"m"-タグシステムの集合はチューリング完全である。すなわち、あるチューリング機械 T について、T をシミュレートする "m"-タグシステムが必ず存在する。特に、2-タグシステムで万能チューリング機械のシミュレートが可能であることが、Wang（1963年）と Cocke & Minsky（1964年）で示されている。逆に、あるチューリング機械でチューリング完全である "m"-タグシステムのクラスをシミュレートできることを示すことで、それが万能チューリング機械であることを示すことができる。例えば、Rogozhin（1996年）は 2-タグシステムのクラスの万能性を証明した。このときの 2-タグシステムのアルファベットは {"a

出典:wikipedia