一种 标签系统,其中 个标签规则(每个规则都具有特殊形式)的列表按顺序应用于系统,然后从第一个规则重新开始。在循环标签系统中,每组标签规则都具有特殊的结构:当且仅当当前模式的第一个元素为 1 时,才附加一个模式;并且无论第一个元素是 0 还是 1,第一个元素都会被删除。
例如,考虑一个由白色和黑色单元格组成的状态,分别标记为 0 和 1,以及循环标签系统 和
,初始状态为
,如上图所示。根据要求,此系统始终删除第一个元素,并且当且仅当第一个单元格为黑色时才附加特定模式。
1. 在第一步中,最左边的元素是 1,因此应用第一个规则得到 ,因为附加了
,然后删除了初始的
。
2. 应用第二个规则在末尾添加 并删除第一个元素,得到
。
3. 再次应用第一个规则在末尾添加 并且(像往常一样)删除第一个元素,得到
。
4. 再次应用第二个规则得到 ,依此类推 (Wolfram 2002, p. 95)。
可以构建一个循环标签系统来模拟任何 图灵机,因此通用的循环标签系统是可能的 (Wolfram 2002, p. 678)。