“朗顿的蚂蚁”的版本间的差异

2020年4月25日 (六) 16:40的版本

朗顿蚂蚁 Langton's ant是元胞自动机 Cellular Automata的例子。它由克里斯托弗·朗顿 Christopher Langton在1986年提出，它由黑白格子和一只“蚂蚁”构成^[1]，是一个二维图灵机。朗顿蚂蚁拥有非常简单的逻辑和复杂的表现。在2000年朗顿蚂蚁的图灵完备性被证明。朗顿蚂蚁的想法后来被推广，比如使用多种颜色和状态的白蚁 Turmite。

11000步后的朗顿蚂蚁图像，红色像素是蚂蚁所在的位置。

规则

前200步朗顿蚂蚁的动态图

在平面上的正方形格被填上黑色或白色。我们把任意一个正方形定义为“蚂蚁”。它的头部朝向上下左右其中一方。“蚂蚁”按照下列规则行动：

若蚂蚁在白格，右转90度，将该格改为黑格，向前移一步；
若蚂蚁在黑格，左转90度，将该格改为白格，向前移一步。

朗顿的蚂蚁也可以被描述成一种细胞自动机，其中网格被涂成黑色或白色，“蚂蚁”所在的方块有八种不同颜色中的一种，它们被分配来编码黑/白状态的组合和蚂蚁当前的运动方向。^[2]

行为模式

这些简单的规则会导致复杂的行为。从完全白色的网格开始时，三种明显的行为模式是显而易见的。

简单 Simplicity。在最初的几百次移动中，它创建了非常简单的模式，这些模式通常是对称的。
混乱 Chaos。经过几百次移动，一个大的、不规则的黑白格子出现了。直到大约10,000步后，蚂蚁沿着一条伪随机路径直线行进。
突然出现的规则 Emergent order。最终，蚂蚁开始建立一个无限重复的104步循环“高速公路”模式。

若从全白的背景开始，在一开始的数百步，蚂蚁留下的路线会出现许多对称或重复的形状，然后会出现类似混沌的假随机，大至约一万步后会出现以104步为周期无限重复的“高速公路”朝固定方向移动^[3]。在目前试过的所有起始状态，蚂蚁的路线最终都会变成高速公路，但尚无法证明这是任何一个起始状态都会导致的必然结果^[4]。

代码部分即为该行为的演示。

NetLogo代码实现

源代码

to setup
  clear-all
  create-turtles 1[
    set heading random 1 * 90
  ]
  reset-ticks
end

to go
  ask turtles[
    ifelse pcolor = white[
      right 90
      set pcolor black
      forward 1
    ][
      left 90
      set pcolor  white
      forward 1
    ]
  ]
  tick
end

运行演示

普遍性

在2000年，Gajardo等人展示了一种使用朗顿蚂蚁的单个实例的轨迹来计算任何布尔电路的构造，此外，还可以使用该蚂蚁的轨迹来模拟任意图灵机进行计算。这意味着该蚂蚁具有通用计算能力。

推广到多种颜色

Greg Turk 和 Jim Propp 考虑一个关于朗顿蚂蚁的简单的扩展，除了两种颜色分别让蚂蚁左转或右转，也可以定义更多种颜色进行循环。通用的表示方法是用L和R依序表示各颜色是左转还是右转，朗顿蚂蚁的规则即可表示为RL。有些规则会产生对称或重复的形状。这些扩展的朗顿蚂蚁中的一些产生的图案一次又一次变得对称。一个最简单的例子就是ant“RLLR”。这种情况发生的一个充分条件是，将蚂蚁的名字看作一个循环列表，它由连续对相同的字母“LL”或“RR”组成。(术语“循环列表”表明最后一个字母与第一个字母配对)这个证明涉及到Truchet tiles。

RLR: 混沌的生长，没有证实会产生高速公路
LLRR: 对称的生长
LRRRRRLLR: 形成方块
LLRRRLRLRLLR: 生成高速公路
RRLLLRLLLRRR: 生成一个移动并生长的实心三角形
L2NNL1L2L1: 六边形循环生长
L1L2NUL2L1R2: 六边形螺旋生长

六边形网格允许多达六种不同的旋转，这里记录为n(没有变化)，R1(60顺时针方向)，R2(120顺时针方向)，U(180)，L2(120逆时针方向)，L1(60逆时针方向)。

扩展到多种状态

朗顿蚂蚁的进一步扩展是考虑Turing机器的多种状态——就好像蚂蚁本身的颜色可以改变。这些蚂蚁被称为“ Turmites”，即“ Turing machine ant”的缩写。常见行为包括产生高速公路，混乱增长和螺旋增长。

螺旋增长
半混乱增长
经过一段时间的混乱增长后的高速公路
具有独特的纹理的混沌生长
在扩大的框架内具有独特纹理的增长
构造斐波那契螺旋

扩展到多只蚂蚁

多只朗顿的蚂蚁可以共存于2D平面上，它们的相互作用产生了复杂的高阶自动机，这些自动机共同构建了多种有组织的结构。我们不需要解决冲突，因为坐在格上的每个蚂蚁都希望对黑白盘进行相同的更改。通过这个视频可以看到这些。只需要制定一个规则，当它们相遇时，多个turmits就可以共存于2D平面上。Ed Pegg, Jr.认为当他们相遇时，可以制定一分为二或互相消灭的规则。

参考文献

↑ C.G.Langton (1986) Studying artificial life with cellular automata.Physica D.22.1-3:(120-149)
↑ Gajardo, A., Moreira, A., Goles, E. (2002) "Complexity of Langton's ant.(15 March, Discrete Applied Mathematics.117, 10.(41--50, S0166, 00334--6)
↑ Pratchett (1999) The Science Of Discworld.
↑ Bunimovich (1992) Recurrence properties of Lorentz lattice gas cellular automata.Journal of Statistical Physics.67, 10.(289--302)

外部链接

广义的蚂蚁 Generalized Ants
朗顿的蚂蚁：生命和命运 Langton's Ant: Life and Deeds

Wolfram MathWorld 关于朗顿蚂蚁的介绍 Weisstein, Eric W. "Langton's ant". MathWorld.
基于JavaScript的可操作界面，可以用来模拟朗顿的蚂蚁，界面化的调试参数Interactive JavaScript-based Langton's ant simulation
在线版本的关于朗顿蚂蚁的演示 Online demonstration of Langton's ant
Youtube上的一个视频，介绍的是朗顿蚁群 Chris Langton demonstrating multiple ants interacting in a "colony"
广义的蚂蚁，这是和《蚂蚁一起旅行》文章的补充材料Generalized ants
一个在线交互版本的例子 An online interactive example
基于JavaScript的演示 JavaScript demonstration
具有多种颜色和可编程蚂蚁的 javaapplet Java applet with multiple colours and programmable ants
3维的朗顿的蚂蚁（例子和程序模版）Langton's ant in 3-D (examples and small demo program)
更多关于朗顿的蚂蚁的3维实现One more implementation of Langton's ant in 3-D
伊恩·斯图尔特 Ian Stewart在数学再创作专栏 Mathematical Recreations column 中使用朗顿的蚂蚁作为万物的理论 theory of everything的隐喻。并证明了朗顿的蚂蚁是无界的。
在多个网格和可编辑图形上的 Java 小程序，它展示了蚂蚁如何计算逻辑门
在python中使用Pygame对朗顿的蚂蚁编程。
不同的多色朗顿蚂蚁的视频演示
朗顿蚂蚁多色扩展中用于生成规则的 Golly 脚本
在C++中的Simple DirectMedia Layer（SDL 1.2）自定义设置的朗顿的蚂蚁应用程序
遗传数据 DataGenetics, 朗顿的蚂蚁：生命
Windows10系统的桌面应用 Windows 10 desktop application

编者推荐

朗顿的蚂蚁

来自CSDN上的一篇博文蓝桥杯之兰顿蚂蚁- CSDN博客

来自集智俱乐部的一篇微信公众号推文什么是元胞自动机？

本文里涉及朗顿蚂蚁（Langton's ant）作为元胞自动机的例子。

Complexity of Langton's ant

这篇文献中作者给出一个计算任何布尔电路与轨迹的一个单一蚂蚁。通过对一维元胞自动机和图灵机的模拟，证明了系统的p-硬度 p-hardness，并揭示了蚂蚁的普遍性和与之相关的一些问题的不可判定性。

【朗顿蚂蚁】蚂蚁进化出修高速公路的技能！

在Netlogo中模拟“蚂蚁”的运动轨迹，程序很简单，只有两条规则，却形成了复杂的看似智能的复杂系统。这是否是生命的终极答案？

本中文词条由Meng莫和费米子编辑，欢迎在讨论页面留言。

本词条内容源自wikipedia及公开资料，遵守 CC3.0协议。

[1] C.G.Langton (1986) Studying artificial life with cellular automata.Physica D.22.1-3:(120-149)

[2] Gajardo, A., Moreira, A., Goles, E. (2002) "Complexity of Langton's ant.(15 March, Discrete Applied Mathematics.117, 10.(41--50, S0166, 00334--6)

[3] Pratchett (1999) The Science Of Discworld.

[4] Bunimovich (1992) Recurrence properties of Lorentz lattice gas cellular automata.Journal of Statistical Physics.67, 10.(289--302)

[1]

[2]

[3]

[4]

@@ 第19行： / 第19行： @@
 == 行为模式 ==
 这些简单的规则会导致复杂的行为。从完全白色的网格开始时，三种明显的行为模式是显而易见的。
-#  简单。在最初的几百次移动中，它创建了非常简单的模式，这些模式通常是对称的。
+#  简单 Simplicity。在最初的几百次移动中，它创建了非常简单的模式，这些模式通常是对称的。
-#  混乱。经过几百次移动，一个大的、不规则的黑白格子出现了。直到大约10,000步后，蚂蚁沿着一条伪随机路径直线行进。
+#  混乱 Chaos。经过几百次移动，一个大的、不规则的黑白格子出现了。直到大约10,000步后，蚂蚁沿着一条伪随机路径直线行进。
-#  突然出现的规则。最终，蚂蚁开始建立一个无限重复的104步循环“高速公路”模式。
+#  突然出现的规则 Emergent order。最终，蚂蚁开始建立一个无限重复的104步循环“高速公路”模式。
-若从全白的背景开始，在一开始的数百步，蚂蚁留下的路线会出现许多对称或重复的形状，然后会出现类似混沌的假随机，大至约一万步后会出现以104步为周期无限重复的“高速公路”朝固定方向移动<ref >Pratchett (1999) [https://pattern.swarma.org/paper?id=40d7beec-6e8c-11ea-a17c-0242ac1a0005 The Science Of Discworld].</ref>。在目前试过的所有起始状态，蚂蚁的路线最终都会变成高速公路，但尚无法证明这是无论任何起始状态都会导致的必然结果<ref >Bunimovich (1992) [https://pattern.swarma.org/paper?id=ca89b97e-6e8c-11ea-abf3-0242ac1a0005 Recurrence properties of Lorentz lattice gas cellular automata].Journal of Statistical Physics.67, 10.(289--302)</ref>。
+若从全白的背景开始，在一开始的数百步，蚂蚁留下的路线会出现许多对称或重复的形状，然后会出现类似混沌的假随机，大至约一万步后会出现以104步为周期无限重复的“高速公路”朝固定方向移动<ref >Pratchett (1999) [https://pattern.swarma.org/paper?id=40d7beec-6e8c-11ea-a17c-0242ac1a0005 The Science Of Discworld].</ref>。在目前试过的所有起始状态，蚂蚁的路线最终都会变成高速公路，但尚无法证明这是任何一个起始状态都会导致的必然结果<ref >Bunimovich (1992) [https://pattern.swarma.org/paper?id=ca89b97e-6e8c-11ea-abf3-0242ac1a0005 Recurrence properties of Lorentz lattice gas cellular automata].Journal of Statistical Physics.67, 10.(289--302)</ref>。
 代码部分即为该行为的演示。