“集智百科精选”是一个长期专栏，持续为大家推送复杂性科学相关的基本概念和资源信息。作为集智俱乐部的开源科学项目，集智百科希望打造复杂性科学领域最全面的百科全书，欢迎对复杂性科学感兴趣、热爱知识整理和分享的朋友加入！

本文是对集智百科中“朗顿的的蚂蚁”词条的摘录，参考资料及相关词条请参阅百科词条原文。
本词条由集智俱乐部众包生产，难免存在纰漏和问题，欢迎大家留言反馈或者前往对应的百科词条页面进行修改，一经修改，可以获得对应的积分奖励噢！
目录
一、规则
二、行为模式
三、NetLogo代码实现
四、普遍性
五、推广到多种颜色

六、扩展到多种状态
七、扩展到多只蚂蚁
八、编者推荐
九、百科项目志愿者招募
朗顿蚂蚁 Langton's ant是元胞自动机 Cellular Automata的例子。它由克里斯托弗·朗顿 Christopher Langton在1986年提出，它由黑白格子和一只“蚂蚁”构成，是一个二维图灵机。朗顿蚂蚁拥有非常简单的逻辑和复杂的表现。在2000年朗顿蚂蚁的图灵完备性被证明。朗顿蚂蚁的想法后来被推广，比如使用多种颜色和状态的白蚁 Turmite。
11000步后的朗顿蚂蚁图像，红色像素是蚂蚁所在的位置。
规则
前200步朗顿蚂蚁的动态图
在平面上的正方形格被填上黑色或白色。我们把任意一个正方形定义为“蚂蚁”。它的头部朝向上下左右其中一方。“蚂蚁”按照下列规则行动：
  • 若蚂蚁在白格，右转90度，将该格改为黑格，向前移一步；
  • 若蚂蚁在黑格，左转90度，将该格改为白格，向前移一步。
朗顿的蚂蚁也可以被描述成一种细胞自动机，其中网格被涂成黑色或白色，“蚂蚁”所在的方块有八种不同颜色中的一种，它们被分配来编码黑/白状态的组合和蚂蚁当前的运动方向。
行为模式
这些简单的规则会导致复杂的行为。从完全白色的网格开始时，三种明显的行为模式是显而易见的。
  1. 简单 Simplicity。在最初的几百次移动中，它创建了非常简单的模式，这些模式通常是对称的。
  2. 混乱 Chaos。经过几百次移动，一个大的、不规则的黑白格子出现了。直到大约10,000步后，蚂蚁沿着一条伪随机路径直线行进。
  3. 突然出现的规则 Emergent order。最终，蚂蚁开始建立一个无限重复的104步循环“高速公路”模式。
若从全白的背景开始，在一开始的数百步，蚂蚁留下的路线会出现许多对称或重复的形状，然后会出现类似混沌的假随机，大至约一万步后会出现以104步为周期无限重复的“高速公路”朝固定方向移动。在目前试过的所有起始状态，蚂蚁的路线最终都会变成高速公路，但尚无法证明这是任何一个起始状态都会导致的必然结果。
NetLogo代码实现
源代码
to setup
clear
-all
create
-
turtles
1
[
set
heading random
1*90
]
reset
-
ticks
end
to go
ask turtles[
ifelse pcolor
=
white[
right
90set
pcolor black
forward
1
][
left
90set
pcolor white
forward
1
]
]
tick
end
普遍性
在2000年，Gajardo等人展示了一种使用单个朗顿蚂蚁的轨迹来计算任何布尔电路的构造，此外，还可以使用该蚂蚁的轨迹来模拟任意图灵机进行计算。[5] 这意味着该蚂蚁具有通用计算能力。
推广到多种颜色
Greg Turk 和 Jim Propp 考虑一个关于朗顿蚂蚁的简单的扩展，除了使用两种颜色分别让蚂蚁左转或右转，也可以定义更多种颜色进行循环。[6]通用的表示方法是用L和R依序表示各颜色是左转还是右转，朗顿蚂蚁的规则即可表示为RL。有些规则会产生对称或重复的形状。
这些扩展的朗顿蚂蚁中的一些产生的图案一次又一次变得对称。一个最简单的例子就是ant“RLLR”。这种情况发生的一个充分条件是，将蚂蚁的名字看作一个循环列表，它由连续相同的字母“LL”或“RR”组成。
一些多色朗顿的蚂蚁的扩展范例:
六种不同的旋转，这里记录为n(没有变化)，R1(60顺时针方向)，R2(120顺时针方向)，U(180)，L2(120逆时针方向)，L1(60逆时针方向)。
扩展到多种状态
朗顿蚂蚁的进一步扩展是考虑Turing机器的多种状态——就好像蚂蚁本身的颜色可以改变。这些蚂蚁被称为“ Turmites”，即“ Turing machine ant”的缩写。常见行为包括产生高速公路，混乱增长和螺旋增长。
一些白蚁 Turmite 的例子：
扩展到多只蚂蚁
多只朗顿的蚂蚁可以共存于2D平面上，它们的相互作用产生了复杂的高阶自动机，这些自动机共同构建了多种有组织的结构。我们不需要解决冲突，因为坐在格上的每个蚂蚁都希望对黑白盘进行相同的更改。通过这个视频可以看到这些。只需要制定一个规则，当它们相遇时，多个turmits就可以共存于2D平面上。Ed Pegg, Jr.认为当他们相遇时，可以制定一分为二或互相消灭的规则。
编者推荐
    朗顿的蚂蚁
  • 集智俱乐部NetLogo书籍、课程与社群
集智俱乐部新书上市 | NetLogo开荒之作！
  • 来自CSDN上的一篇博文蓝桥杯之兰顿蚂蚁- CSDN博客
https://blog.csdn.net/u011488028/article/details/49643135?
本文里涉及朗顿蚂蚁（Langton's ant）作为元胞自动机的例子。
  • Complexity of Langton's ant
https://pattern.swarma.org/paper?id=5e19d162-6e8b-11ea-b972-0242ac1a0005
这篇文献中作者给出一个计算任何布尔电路与轨迹的一个单一蚂蚁。通过对一维元胞自动机和图灵机的模拟，证明了系统的p-硬度 p-hardness，并揭示了蚂蚁的普遍性和与之相关的一些问题的不可判定性。
  • 【朗顿蚂蚁】蚂蚁进化出修高速公路的技能！
https://www.bilibili.com/video/av32493694/
在Netlogo中模拟“蚂蚁”的运动轨迹，程序很简单，只有两条规则，却形成了复杂的看似智能的复杂系统。这是否是生命的终极答案？
百科项目志愿者招募
作为集智百科项目团队的成员，本文内容由Meng莫和费米子编辑。我们也为每位作者和志愿者准备了专属简介和个人集智百科主页，更多信息可以访问其集智百科个人主页。
以上内容都是我们做这项目的起点，作为来自不同学科和领域的志愿者，我们建立起一个有效的百科团队，分配有审校、翻译、编辑、宣传等工作。我们秉持：知识从我而来，问题到我为止的信念，认真负责编撰每一个词条。
在这里从复杂性知识出发与伙伴同行，同时我们希望有更多志愿者加入这个团队，使百科词条内容得到扩充，并为每位志愿者提供相应奖励与资源，建立个人主页与贡献记录，使其能够继续探索复杂世界。
如果你有意参与更加系统精细的分工，扫描二维码填写报名表，我们期待你的加入！
集智百科报名表
来源：集智百科
编辑：王建萍
推荐阅读
点击“阅读原文”，阅读词条朗顿的蚂蚁原文与参考文献
继续阅读
阅读原文
关键词
集智
集智百科
元胞自动机
词条
规则