朗顿的蚂蚁

来自集智百科 - 复杂系统|人工智能|复杂科学|复杂网络|自组织
费米子（讨论 | 贡献）2020年4月25日 (六) 16:41的版本 （→‎普遍性）
跳到导航 跳到搜索


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

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

规则

前200步朗顿蚂蚁的动态图

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

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

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

行为模式

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

  1. 简单 Simplicity。在最初的几百次移动中，它创建了非常简单的模式，这些模式通常是对称的。
  2. 混乱 Chaos。经过几百次移动，一个大的、不规则的黑白格子出现了。直到大约10,000步后，蚂蚁沿着一条伪随机路径直线行进。
  3. 突然出现的规则 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等人展示了一种使用单个朗顿蚂蚁的轨迹来计算任何布尔电路的构造，此外，还可以使用该蚂蚁的轨迹来模拟任意图灵机进行计算。[5] 这意味着该蚂蚁具有通用计算能力。

推广到多种颜色

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.认为当他们相遇时，可以制定一分为二或互相消灭的规则。

相关词条

由约翰·何顿·康威 John Horton Conway设计的二维元胞自动机
在1984年由克里斯托弗·兰顿研究的一个在特定细胞自动机规则下的自我复制模式
模拟进食行为的细胞自动机族
一个有方向和当前状态的图灵机和一个由无限的二维细胞网格组成的“磁带”

参考文献

  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)
  5. ↑ Gajardo, A.; Moreira, A.; Goles, E. (15 March 2002). "Complexity of Langton's ant" (PDF). Discrete Applied Mathematics. 117 (1–3): 41–50. doi:10.1016/S0166-218X(00)00334-6.

外部链接

编者推荐

朗顿的蚂蚁
本文里涉及朗顿蚂蚁（Langton's ant）作为元胞自动机的例子。
这篇文献中作者给出一个计算任何布尔电路与轨迹的一个单一蚂蚁。 通过对一维元胞自动机和图灵机的模拟，证明了系统的p-硬度 p-hardness，并揭示了蚂蚁的普遍性和与之相关的一些问题的不可判定性。
在Netlogo中模拟“蚂蚁”的运动轨迹，程序很简单，只有两条规则，却形成了复杂的看似智能的复杂系统。这是否是生命的终极答案？

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


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

取自“https://wiki.swarma.org/index.php?title=朗顿的蚂蚁&oldid=5337”