主题
Search

Turmite


Turmite,也称为转向机,是二维图灵机,其中“磁带”由网格空间组成,这些空间可以被一个活动的(“头”)元素写入和擦除,该元素在每次迭代时根据其当前网格方格的状态进行转向。系统的“头”通常在正方形网格上称为“触角”、“蚂蚁”或“turmite”,在六边形网格上称为“蜜蜂”、“蠕虫”或“海龟”。(术语“海龟”是以西摩·帕珀特的海龟几何命名的)。Turmite 跟踪其位置、方向和当前状态。

TurmiteBinaryRule
TurmiteBinaryFrames
Binary-counting turmite

令人惊讶的是,上面规则所示的 turmite 模仿了二进制计数。在这个 turmite 中,红线以上的条带模式对应于递增的二进制数字。在每个周期构建上部模式之后,产生相同的模式(左右镜像)在红线下方。

Turmite highways
TurmiteHighwaysRules

上面的图显示了一些 turmite 的示例,这些 turmite 构建了向下和向右移动的结构,称为“高速公路”(顶部图)及其底层规则(底部图)。左侧的 turmite 被称为兰顿蚂蚁,是最著名的 turmite。第二个 turmite 显示了一个 2 状态 2 色规则,该规则本质上等同于兰顿蚂蚁。在这个规则中,如果状态为 1 且底层单元格为灰色,则单元格变为白色,状态变为 2,并且 turmite 左转。

More turmite highways

上面说明了具有其他可能方向的高速公路。在第三张图中,高速公路随着长度的增加而变粗。

Turmites growing around the edges

边缘周围的生长是常见的。第四张图说明了一个 turmite,即使在稀疏随机数据字段中也会生长。

Turmite spirals

螺旋线非常常见。上面的第二个 turmite 构建了一个黄金矩形

Chaotic turmites 1
Chaotic turmites 2

可能会发生许多不同类型的混沌行为。例如,第一行中的第四个 turmite 显示了一种递增计数的行为。

Turmite busy beaver

除了持久结构、嵌套生长和混沌行为之外,turmite 还可能在任意大小的循环中循环。没有已知的程序可以确定对于一般的 turmite 是否会发生这种情况。上面的图示显示了一个 turmite,它在经过一定量的生长后陷入循环。


另请参阅

停机问题, 兰顿蚂蚁, Paterson 蠕虫, 图灵机

此条目由 Ed Pegg, Jr. 贡献 (作者链接)

使用 Wolfram|Alpha 探索

参考文献

Gajardo-Schulz, A. Influence du réseau spatial sur le comportement d'un système dynamique: la fourmi de Langton. 博士论文. Lyon, France: Computer Science Laboratory, ENS Lyon, 2001 年 6 月. http://www.ens-lyon.fr/LIP/Pub/PhD2001.html.Pegg, E. Jr. "Math Games: 2D Turing Machines." 2004 年 6 月 7 日. http://www.maa.org/editorial/mathgames/mathgames_06_07_04.html.Wolfram, S. 一种新科学。 Champaign, IL: Wolfram Media, 页 930, 2002.

在 Wolfram|Alpha 中被引用

Turmite

请引用为

Pegg, Ed Jr. "Turmite." 来自 MathWorld--Wolfram Web 资源,由 Eric W. Weisstein 创建. https://mathworld.net.cn/Turmite.html

主题分类