标签系统是一组规则，用于指定从序列开头移除固定数量的元素（通常表示为 
或 
），并根据从开头移除的元素，将一组元素附加（“标记”到末尾）。例如，考虑上图所示的 
标签系统，其中黑色代表 1，白色代表 0。然后起始模式是“1”，转换规则是 
和 
（Wolfram 2002, 第 93页）。
标签系统最早由 Post 于 1920 年提出（Wolfram 2002, 第 894页），尽管这些结果直到很久之后才广为人知（Post 1943）。Post 显然研究了某种类型的标签系统，该系统在每一步中涉及移除和添加不超过两个元素，并得出结论，它们都没有产生复杂的行为。然而，在研究每一步移除三个元素的规则时，他发现一个特定的规则随着初始条件的变化而变化很大（Wolfram 2002, 第 894-895页）。一般来说，如果添加的数量永远不大于删除的数量，则结果行为最多是循环的。因此，允许添加任意长度的元素可以提供最有趣和复杂的行为。
标签系统具有类似图灵机的停机问题，用于根据任意给定的初始序列来判断，重复应用规则是否会导致单词长度小于从开头移除的元素数量。通过证明任何图灵机都可以表示为标签系统，Minsky (1961) 证明了标签系统中普遍性和不可判定停机的存在，这一结果随后被 Cocke 和 Minsky (1964) 以及 Wang (1963; Wolfram 2002, 第 1120页) 改进。Wang (1963) 还考虑了一种与标签系统相反的系统，他称之为滞后系统。Maslov (1964) 表明，对于任何 
，都存在一个标签系统，使得 Post 提出的两种形式的标签系统都是不可解的。
