主题
Search

循环标签系统


一种 标签系统,其中 n 个标签规则(每个规则都具有特殊形式)的列表按顺序应用于系统,然后从第一个规则重新开始。在循环标签系统中,每组标签规则都具有特殊的结构:当且仅当当前模式的第一个元素为 1 时,才附加一个模式;并且无论第一个元素是 0 还是 1,第一个元素都会被删除。

CyclicTagSystem

例如,考虑一个由白色和黑色单元格组成的状态,分别标记为 0 和 1,以及循环标签系统 {(1,...)->(...,1,1),(0,...)->(...)}{(1,...)->(...,1,0),(0,...)->(...)},初始状态为 (1),如上图所示。根据要求,此系统始终删除第一个元素,并且当且仅当第一个单元格为黑色时才附加特定模式。

1. 在第一步中,最左边的元素是 1,因此应用第一个规则得到 (1,1),因为附加了 (1,1),然后删除了初始的 (1)

2. 应用第二个规则在末尾添加 (1,0) 并删除第一个元素,得到 (1,1,0)

3. 再次应用第一个规则在末尾添加 (1,1) 并且(像往常一样)删除第一个元素,得到 (1,0,1,1)

4. 再次应用第二个规则得到 (0,1,1,1,0),依此类推 (Wolfram 2002, p. 95)。

可以构建一个循环标签系统来模拟任何 图灵机,因此通用的循环标签系统是可能的 (Wolfram 2002, p. 678)。


另请参阅

字符串重写系统, 替换系统, 标签系统

相关 Wolfram 站点

http://atlas.wolfram.com/06/03/

此条目部分内容由 Todd Rowland 贡献

使用 Wolfram|Alpha 探索

参考文献

Wolfram, S. 一种新的科学。 Champaign, IL: Wolfram Media, pp. 95-96 和 895, 2002.

Wolfram|Alpha 参考

循环标签系统

引用为

Rowland, ToddWeisstein, Eric W. "循环标签系统。" 来自 MathWorld--Wolfram 网络资源。 https://mathworld.net.cn/CyclicTagSystem.html

主题分类