標籤系統是一組規則，用於指定從序列開頭移除固定數量的元素（通常表示為 
或 
），並根據從開頭移除的元素，將一組元素附加（“標記”到末尾）。例如，考慮上圖所示的 
標籤系統，其中黑色代表 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 提出的兩種形式的標籤系統都是不可解的。
