タグシステム
停止記号を使った単純な 2-タグシステムの例を以下に示す。
上述の定義は、ポストが1943年に発表した当時のものとは異なる。ポストの定義では停止記号がなく、空の単語についてのみ停止するようになっていて、タグ操作 t は次のように定義されていた。
空でない単語 S の左端の記号を x としたとき、t(S) は最初に単語 P(x) を S の右に追加し、次に左端から m 個の記号を削除する。記号数が m 個未満なら、全記号を削除する。
下線を引いた部分は、m-タグシステムのチューリング完全性を考慮したものである。