504
个编辑
更改
跳到导航
跳到搜索
无编辑摘要
{{#seo:
|keywords=朗顿的蚂蚁,Cellular Automata,元胞自动机, Langton's ant
|description=元胞自动机,复杂系统
}}
'''朗顿蚂蚁'''（Langton's ant）是[[元胞自动机]]的例子。它由[[克里斯托弗·朗顿 Christopher Langton]]在1986年提出，它由黑白格子和一只“蚂蚁”构成<ref >C.G.Langton (1986) [https://pattern.swarma.org/paper?id=074d27dc-5386-11ea-be1d-0242ac1a0005 Studying artificial life with cellular automata].Physica D.22.1-3:(120-149)</ref>，是一个二维图灵机。朗顿蚂蚁拥有非常简单的逻辑和复杂的表现。在2000年朗顿蚂蚁的图灵完备性被证明。朗顿蚂蚁的想法后来被推广，比如使用多种颜色和状态。[[File:蚂蚁图像.png | right| thumb | 11000步后的朗顿蚂蚁图像，红色像素是蚂蚁所在的位置。]]
== 规则==
[[File:朗顿蚂蚁动态图.gif|500px|right|thumb|前200步朗顿蚂蚁的动态图]]
在平面上的正方形格被填上黑色或白色。我们随意地把一个正方形定义为“蚂蚁”。它的头部朝向上下左右其中一方。“蚂蚁”按照下列规则行动：
* 若蚂蚁在白格，右转90度，将该格改为黑格，向前移一步；
* 若蚂蚁在黑格，左转90度，将该格改为白格，向前移一步。
朗顿的蚂蚁也可以被描述成一种细胞自动机，其中网格被涂成黑色或白色，“蚂蚁”所在的方块有八种不同颜色中的一种，它们被分配来编码黑/白状态的组合和蚂蚁当前的运动方向。<ref >Gajardo, A., Moreira, A., Goles, E. (2002) [https://pattern.swarma.org/paper?id=5e19d162-6e8b-11ea-b972-0242ac1a0005 "Complexity of Langton's ant].(15 March, Discrete Applied Mathematics.117, 10.(41--50, S0166, 00334--6)</ref>
== 行为模式 ==
这些简单的规则会导致复杂的行为。从完全白色的网格开始时，三种明显的行为模式是显而易见的。
# 简单。在最初的几百次移动中，它创建了非常简单的模式，这些模式通常是对称的。
# 混乱。经过几百次移动，一个大的、不规则的黑白格子出现了。直到大约10,000步后，蚂蚁沿着一条伪随机路径直线行进。
# 突然出现的规则。最终，蚂蚁开始建立一个无限重复的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>。
代码部分即为该行为的演示。
== NetLogo代码实现 ==
===源代码===
<syntaxhighlight lang="python">
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
</syntaxhighlight>
===运行演示===
[[File:Gof.gif| 代码演示界面 ]]
== 普遍性==
在2000年，Gajardo等人展示了一种使用朗顿蚂蚁的单个实例的轨迹来计算任何布尔电路的构造，此外，还可以使用该蚂蚁的轨迹来模拟任意图灵机进行计算。 这意味着该蚂蚁具有通用计算能力。
== 推广到多种颜色 ==
Greg Turk 和 Jim Propp 考虑一个关于朗顿蚂蚁的简单的扩展，除了两种颜色分别让蚂蚁左转或右转，也可以定义更多种颜色进行循环。通用的表示方法是用L和R依序表示各颜色是左转还是右转，朗顿蚂蚁的规则即可表示为RL。有些规则会产生对称或重复的形状。
这些扩展的朗顿蚂蚁中的一些产生的图案一次又一次变得对称。一个最简单的例子就是ant“RLLR”。这种情况发生的一个充分条件是，将蚂蚁的名字看作一个循环列表，它由连续对相同的字母“LL”或“RR”组成。(术语“循环列表”表明最后一个字母与第一个字母配对)这个证明涉及到[https://en.wikipedia.org/wiki/Truchet_tiles Truchet tiles]。
<gallery>
File:混沌的生长.png|RLR: 混沌的生长，没有证实会产生高速公路
File:对称的生长.png|LLRR: 对称的生长
File:LRRRRRLLR.png|LRRRRRLLR: 形成方块
File:LLRRRLRLRLLR.png|LLRRRLRLRLLR: 生成高速公路
File:RRLLLRLLLRRR.png|RRLLLRLLLRRR: 生成一个移动并生长的实心三角形
File:L2NNL1L2L1.png|L2NNL1L2L1: 六边形循环生长
File:L1L2NUL2L1R2.png|L1L2NUL2L1R2: 六边形螺旋生长
</gallery>
六边形网格允许多达六种不同的旋转，这里记录为n(没有变化)，R1(60顺时针方向)，R2(120顺时针方向)，U(180)，L2(120逆时针方向)，L1(60逆时针方向)。
==扩展到多种状态==
朗顿蚂蚁的进一步扩展是考虑Turing机器的多种状态——就好像蚂蚁本身的颜色可以改变。 这些蚂蚁被称为“ Turmites”，即“ Turing machine ant”的缩写。 常见行为包括产生高速公路，混乱增长和螺旋增长。
<gallery>
File:螺旋增长.png|螺旋增长
File:半混乱增长.png|半混乱增长
File:高速公路.png|经过一段时间的混乱增长后的高速公路
File:混沌生长.png|具有独特的纹理的混沌生长
File:纹理增长.png |在扩大的框架内具有独特纹理的增长
File:构造斐波那契螺旋.png|构造斐波那契螺旋
</gallery>
==扩展到多只蚂蚁 ==
多只朗顿的蚂蚁可以共存于2D平面上，它们的相互作用产生了复杂的高阶自动机，这些自动机共同构建了多种有组织的结构。我们不需要需解决冲突，因为坐在格上的每个蚂蚁都希望对黑白盘进行相同的更改。通过[https://www.youtube.com/watch?v=w6XQQhCgq5c 这个视频]可以看到这些。
只需要制定一个规则，当它们相遇时，多个turmits就可以共存于2D平面上。[https://en.wikipedia.org/wiki/Ed_Pegg,_Jr. Ed Pegg, Jr.]认为当他们相遇时，可以制定一分为二或互相消灭的规则。
==参考文献 ==
<references/>
==外部链接 ==
* [http://www.math.sunysb.edu/~scott/ants/ Generalized Ants ]
* [https://web.archive.org/web/20080208220623/http://www.ing-mat.udec.cl/~anahi/langton/general.html Langton's Ant: Life and Deeds]
* Wolfram MathWorld 关于朗顿蚂蚁的介绍 Weisstein, Eric W. [http://mathworld.wolfram.com/LangtonsAnt.html "Langton's ant"]. MathWorld.
*基于JavaScript的可操作界面，可以用来模拟朗顿的蚂蚁，界面化的调试参数[https://tomdenottelander.com/projects/langtonsant/index.html Interactive JavaScript-based Langton's ant simulation]
*在线版本的关于朗顿蚂蚁的演示 [http://www.math.ubc.ca/~cass/www/ant/ant.html Online demonstration of Langton's ant]
*Youtube上的一个视频，介绍的是朗顿蚁群 [https://www.youtube.com/watch?v=w6XQQhCgq5c Chris Langton demonstrating multiple ants interacting in a "colony"]
* 广义的蚂蚁，这是和《蚂蚁一起旅行》文章的补充材料[http://www.math.sunysb.edu/~scott/ants/ Generalized ants]
*一个在线交互版本的例子 [http://rossscrivener.co.uk/blog/langtons-ants-in-javascript An online interactive example]
*基于JavaScript的演示 [https://web.archive.org/web/20110225042238/http://skyward.nefec.org/langstonsAnt.php JavaScript demonstration]
* [https://web.archive.org/web/20030417162203/http://www.hut.fi/~jblomqvi/langton/index.html Java applet with multiple colours and programmable ants]
* [http://heikohamann.de/langtonsAnt/langtons_ant_3d.html Langton's ant in 3-D (examples and small demo program)]
* [https://www.youtube.com/watch?v=0iyDQxaivh0 One more implementation of Langton's ant in 3-D]
* [https://web.archive.org/web/20160303211426/http://dev.whydomath.org/Reading_Room_Material/ian_stewart/AntyParticles.pdf Mathematical Recreations column] by Ian Stewart (mathematician)|Ian Stewart using Langton's ant as a metaphor for a [https://en.wikipedia.org/wiki/Theory_of_everything theory of everything]. Contains the proof that Langton's ant is unbounded.
* [http://www.ing-mat.udec.cl/~anahi/langton Java applet on several grids and editable graphs, it shows how the ant can compute logical gates]
* [http://www.willmcgugan.com/2007/05/18/langton-ants-in-pygame/ Programming Langton's ants] in Python (programming language) using Pygame.
* [https://www.youtube.com/watch?v=1X-gtr4pEBU A video demo of different multiple-color Langton's ants]
* [https://gollygang.github.io/ruletablerepository/downloads/Langtons-Ant-nColor.zip Golly script for generating rules in the multiple color extension of Langton's ant]
* [http://www.megastormsystems.com/cc-code/langtons-ant Langton's ants application with custom settings], developed in C++ using Simple DirectMedia Layer|SDL 1.2
* [http://datagenetics.com/blog/september22015/index.html DataGenetics, Langton's Ant (and Life)]
*Windows10系统的桌面应用 [https://gliderkite.itch.io/langtons-ant, Windows 10 desktop application]
== 编者推荐==
*来自CSDN上的一篇博文[https://blog.csdn.net/u011488028/article/details/49643135? 蓝桥杯之兰顿蚂蚁- CSDN博客]
*来自集智俱乐部的一篇微信公众号推文[https://swarma.org/?p=18576 什么是元胞自动机？]里面涉及到朗顿蚂蚁（Langton's ant）作为元胞自动机的例子。
本中文词条由[[用户:Meng莫|Meng莫]]编辑，欢迎在讨论页面留言。
'''本词条内容源自wikipedia及公开资料，遵守 CC3.0协议。'''
|keywords=朗顿的蚂蚁,Cellular Automata,元胞自动机, Langton's ant
|description=元胞自动机,复杂系统
}}
'''朗顿蚂蚁'''（Langton's ant）是[[元胞自动机]]的例子。它由[[克里斯托弗·朗顿 Christopher Langton]]在1986年提出，它由黑白格子和一只“蚂蚁”构成<ref >C.G.Langton (1986) [https://pattern.swarma.org/paper?id=074d27dc-5386-11ea-be1d-0242ac1a0005 Studying artificial life with cellular automata].Physica D.22.1-3:(120-149)</ref>，是一个二维图灵机。朗顿蚂蚁拥有非常简单的逻辑和复杂的表现。在2000年朗顿蚂蚁的图灵完备性被证明。朗顿蚂蚁的想法后来被推广，比如使用多种颜色和状态。[[File:蚂蚁图像.png | right| thumb | 11000步后的朗顿蚂蚁图像，红色像素是蚂蚁所在的位置。]]
== 规则==
[[File:朗顿蚂蚁动态图.gif|500px|right|thumb|前200步朗顿蚂蚁的动态图]]
在平面上的正方形格被填上黑色或白色。我们随意地把一个正方形定义为“蚂蚁”。它的头部朝向上下左右其中一方。“蚂蚁”按照下列规则行动：
* 若蚂蚁在白格，右转90度，将该格改为黑格，向前移一步；
* 若蚂蚁在黑格，左转90度，将该格改为白格，向前移一步。
朗顿的蚂蚁也可以被描述成一种细胞自动机，其中网格被涂成黑色或白色，“蚂蚁”所在的方块有八种不同颜色中的一种，它们被分配来编码黑/白状态的组合和蚂蚁当前的运动方向。<ref >Gajardo, A., Moreira, A., Goles, E. (2002) [https://pattern.swarma.org/paper?id=5e19d162-6e8b-11ea-b972-0242ac1a0005 "Complexity of Langton's ant].(15 March, Discrete Applied Mathematics.117, 10.(41--50, S0166, 00334--6)</ref>
== 行为模式 ==
这些简单的规则会导致复杂的行为。从完全白色的网格开始时，三种明显的行为模式是显而易见的。
# 简单。在最初的几百次移动中，它创建了非常简单的模式，这些模式通常是对称的。
# 混乱。经过几百次移动，一个大的、不规则的黑白格子出现了。直到大约10,000步后，蚂蚁沿着一条伪随机路径直线行进。
# 突然出现的规则。最终，蚂蚁开始建立一个无限重复的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>。
代码部分即为该行为的演示。
== NetLogo代码实现 ==
===源代码===
<syntaxhighlight lang="python">
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
</syntaxhighlight>
===运行演示===
[[File:Gof.gif| 代码演示界面 ]]
== 普遍性==
在2000年，Gajardo等人展示了一种使用朗顿蚂蚁的单个实例的轨迹来计算任何布尔电路的构造，此外，还可以使用该蚂蚁的轨迹来模拟任意图灵机进行计算。 这意味着该蚂蚁具有通用计算能力。
== 推广到多种颜色 ==
Greg Turk 和 Jim Propp 考虑一个关于朗顿蚂蚁的简单的扩展，除了两种颜色分别让蚂蚁左转或右转，也可以定义更多种颜色进行循环。通用的表示方法是用L和R依序表示各颜色是左转还是右转，朗顿蚂蚁的规则即可表示为RL。有些规则会产生对称或重复的形状。
这些扩展的朗顿蚂蚁中的一些产生的图案一次又一次变得对称。一个最简单的例子就是ant“RLLR”。这种情况发生的一个充分条件是，将蚂蚁的名字看作一个循环列表，它由连续对相同的字母“LL”或“RR”组成。(术语“循环列表”表明最后一个字母与第一个字母配对)这个证明涉及到[https://en.wikipedia.org/wiki/Truchet_tiles Truchet tiles]。
<gallery>
File:混沌的生长.png|RLR: 混沌的生长，没有证实会产生高速公路
File:对称的生长.png|LLRR: 对称的生长
File:LRRRRRLLR.png|LRRRRRLLR: 形成方块
File:LLRRRLRLRLLR.png|LLRRRLRLRLLR: 生成高速公路
File:RRLLLRLLLRRR.png|RRLLLRLLLRRR: 生成一个移动并生长的实心三角形
File:L2NNL1L2L1.png|L2NNL1L2L1: 六边形循环生长
File:L1L2NUL2L1R2.png|L1L2NUL2L1R2: 六边形螺旋生长
</gallery>
六边形网格允许多达六种不同的旋转，这里记录为n(没有变化)，R1(60顺时针方向)，R2(120顺时针方向)，U(180)，L2(120逆时针方向)，L1(60逆时针方向)。
==扩展到多种状态==
朗顿蚂蚁的进一步扩展是考虑Turing机器的多种状态——就好像蚂蚁本身的颜色可以改变。 这些蚂蚁被称为“ Turmites”，即“ Turing machine ant”的缩写。 常见行为包括产生高速公路，混乱增长和螺旋增长。
<gallery>
File:螺旋增长.png|螺旋增长
File:半混乱增长.png|半混乱增长
File:高速公路.png|经过一段时间的混乱增长后的高速公路
File:混沌生长.png|具有独特的纹理的混沌生长
File:纹理增长.png |在扩大的框架内具有独特纹理的增长
File:构造斐波那契螺旋.png|构造斐波那契螺旋
</gallery>
==扩展到多只蚂蚁 ==
多只朗顿的蚂蚁可以共存于2D平面上，它们的相互作用产生了复杂的高阶自动机，这些自动机共同构建了多种有组织的结构。我们不需要需解决冲突，因为坐在格上的每个蚂蚁都希望对黑白盘进行相同的更改。通过[https://www.youtube.com/watch?v=w6XQQhCgq5c 这个视频]可以看到这些。
只需要制定一个规则，当它们相遇时，多个turmits就可以共存于2D平面上。[https://en.wikipedia.org/wiki/Ed_Pegg,_Jr. Ed Pegg, Jr.]认为当他们相遇时，可以制定一分为二或互相消灭的规则。
==参考文献 ==
<references/>
==外部链接 ==
* [http://www.math.sunysb.edu/~scott/ants/ Generalized Ants ]
* [https://web.archive.org/web/20080208220623/http://www.ing-mat.udec.cl/~anahi/langton/general.html Langton's Ant: Life and Deeds]
* Wolfram MathWorld 关于朗顿蚂蚁的介绍 Weisstein, Eric W. [http://mathworld.wolfram.com/LangtonsAnt.html "Langton's ant"]. MathWorld.
*基于JavaScript的可操作界面，可以用来模拟朗顿的蚂蚁，界面化的调试参数[https://tomdenottelander.com/projects/langtonsant/index.html Interactive JavaScript-based Langton's ant simulation]
*在线版本的关于朗顿蚂蚁的演示 [http://www.math.ubc.ca/~cass/www/ant/ant.html Online demonstration of Langton's ant]
*Youtube上的一个视频，介绍的是朗顿蚁群 [https://www.youtube.com/watch?v=w6XQQhCgq5c Chris Langton demonstrating multiple ants interacting in a "colony"]
* 广义的蚂蚁，这是和《蚂蚁一起旅行》文章的补充材料[http://www.math.sunysb.edu/~scott/ants/ Generalized ants]
*一个在线交互版本的例子 [http://rossscrivener.co.uk/blog/langtons-ants-in-javascript An online interactive example]
*基于JavaScript的演示 [https://web.archive.org/web/20110225042238/http://skyward.nefec.org/langstonsAnt.php JavaScript demonstration]
* [https://web.archive.org/web/20030417162203/http://www.hut.fi/~jblomqvi/langton/index.html Java applet with multiple colours and programmable ants]
* [http://heikohamann.de/langtonsAnt/langtons_ant_3d.html Langton's ant in 3-D (examples and small demo program)]
* [https://www.youtube.com/watch?v=0iyDQxaivh0 One more implementation of Langton's ant in 3-D]
* [https://web.archive.org/web/20160303211426/http://dev.whydomath.org/Reading_Room_Material/ian_stewart/AntyParticles.pdf Mathematical Recreations column] by Ian Stewart (mathematician)|Ian Stewart using Langton's ant as a metaphor for a [https://en.wikipedia.org/wiki/Theory_of_everything theory of everything]. Contains the proof that Langton's ant is unbounded.
* [http://www.ing-mat.udec.cl/~anahi/langton Java applet on several grids and editable graphs, it shows how the ant can compute logical gates]
* [http://www.willmcgugan.com/2007/05/18/langton-ants-in-pygame/ Programming Langton's ants] in Python (programming language) using Pygame.
* [https://www.youtube.com/watch?v=1X-gtr4pEBU A video demo of different multiple-color Langton's ants]
* [https://gollygang.github.io/ruletablerepository/downloads/Langtons-Ant-nColor.zip Golly script for generating rules in the multiple color extension of Langton's ant]
* [http://www.megastormsystems.com/cc-code/langtons-ant Langton's ants application with custom settings], developed in C++ using Simple DirectMedia Layer|SDL 1.2
* [http://datagenetics.com/blog/september22015/index.html DataGenetics, Langton's Ant (and Life)]
*Windows10系统的桌面应用 [https://gliderkite.itch.io/langtons-ant, Windows 10 desktop application]
== 编者推荐==
*来自CSDN上的一篇博文[https://blog.csdn.net/u011488028/article/details/49643135? 蓝桥杯之兰顿蚂蚁- CSDN博客]
*来自集智俱乐部的一篇微信公众号推文[https://swarma.org/?p=18576 什么是元胞自动机？]里面涉及到朗顿蚂蚁（Langton's ant）作为元胞自动机的例子。
本中文词条由[[用户:Meng莫|Meng莫]]编辑，欢迎在讨论页面留言。
'''本词条内容源自wikipedia及公开资料，遵守 CC3.0协议。'''