タグ系とは、文字列の書き換えによって計算を進める形式体系で、エミール・ポストが1943年に導入した。系は削除数と呼ばれる正整数 m、有限のアルファベット、各文字に対応する追加語の組で定義される。各ステップでは、まず文字列の先頭の文字を読み、その文字に割り当てられた語を末尾に付け加え、続けて先頭から m 文字を削除する。この操作を、文字列の長さが m より短くなるか停止文字が現れるまで繰り返す。規則は数行で書き尽くせるほど単純だが、任意の初期文字列が停止するかを判定する問題は一般に決定不能である。
削除数が2の場合を2-タグ系と呼び、計算理論ではとりわけ重要な位置を占める。1960年代にミンスキーが2-タグ系でチューリングマシンをシミュレートできることを示し、この最小限の書き換え規則が万能な計算能力をもつことが確立された。この結果は、少数の状態と記号しかもたない小さな万能チューリングマシンを構成する際の標準的な道具となった。さらに後の研究では、2-タグ系がチューリングマシンの計算を多項式時間でシミュレートできることが示され、効率の面でも大きな損失を伴わないことが明らかになった。
タグ系は数論の反復手続きを表現する形式としても知られる。たとえば、自然数 n を1文字の n 回の並びとして符号化し、3文字のアルファベットに数個の規則を与えるだけで、コラッツ予想の 3n+1 手続きを文字列操作として再現できる。初期文字列によって長さは予測しがたく伸縮し、停止するかどうかを事前に見きわめることはできない。単純な規則系のなかに複雑な振る舞いと計算的万能性が同時に現れる例として、セルオートマトンやレジスタマシンと並んで参照される。