タグシステム
変換 t(タグ操作とも)は、停止単語以外の単語について定義されており、単語 S の左端の記号を x としたとき、t(S) とは S の左端から m 個の記号を削除し、残った部分の右側に単語 P(x) を追加したものである。
タグシステムにおける計算とは、変換 t を繰り返すことで有限単語列を生成することであり、初期状態で何らかの単語が与えられ、停止単語が生成された時点で停止する。なお、この定義では、有限回の繰り返しの間に停止単語が生成されない場合を計算とは呼べない。
この定義で停止記号を使うと、計算結果として最後の単語だけを出力する。一方、停止記号を使わなければ、タグ操作の反復によって生成された単語列全体が出力となる。
典型的な別の定義として、停止記号を使わず、m 未満の長さの単語を全て停止単語とする定義もある。また、ポストが1943年に最初に発表した定義では、空文字列についてのみ停止するようになっていた。