朗顿蚂蚁

来自集智百科 - 复杂系统|人工智能|复杂科学|复杂网络|自组织
跳到导航 跳到搜索

此词条暂由彩云小译翻译，翻译字数共700，未经人工整理和审校，带来阅读不便，请见谅。

不要移除这个！它将被一个小部件填充，这个小部件为那些激活了相应小部件的用户演示了 Langton 的 ant! -- >

文件:LangtonsAnt.png
Langton's ant after 11,000 steps. A red pixel shows the ant's location.

Langton's ant after 11,000 steps. A red pixel shows the ant's location.

11000步后的兰顿蚂蚁。一个红色的像素显示蚂蚁的位置。


Langton's ant is a two-dimensional universal Turing machine with a very simple set of rules but complex emergent behavior. It was invented by Chris Langton in 1986 and runs on a square lattice of black and white cells.[1] The universality of Langton's ant was proven in 2000.[2] The idea has been generalized in several different ways, such as turmites which add more colors and more states.

Langton's ant is a two-dimensional universal Turing machine with a very simple set of rules but complex emergent behavior. It was invented by Chris Langton in 1986 and runs on a square lattice of black and white cells. The universality of Langton's ant was proven in 2000. when starting on a completely white grid.

兰顿的蚂蚁是一个二维的通用图灵机，有一套非常简单的规则，但是有复杂的突发行为。它由克里斯 · 兰顿于1986年发明，运行在黑白电池组成的正方形格子上。兰顿蚂蚁的普遍性在2000年被证明是正确的，当时它是从一个完全白色的栅格开始的。


Rules

Simplicity. During the first few hundred moves it creates very simple patterns which are often symmetric.

简单。在最初的几百次移动中，它创建了非常简单的模式，通常是对称的。

文件:LangtonsAntAnimated.gif
Animation of first 200 steps of Langton's ant

Chaos. After a few hundred moves, a large, irregular pattern of black and white squares appears. The ant traces a pseudo-random path until around 10,000 steps.

混乱。经过几百次移动，一个大的，不规则的黑白格子出现了。蚂蚁沿着一条伪随机路径行进，直到大约10,000步。


Emergent order. Finally the ant starts building a recurrent "highway" pattern of 104 steps that repeats indefinitely.

紧急秩序。最后，蚂蚁开始建立一个循环的“高速公路”模式，104个步骤无限重复。

Squares on a plane are colored variously either black or white. We arbitrarily identify one square as the "ant". The ant can travel in any of the four cardinal directions at each step it takes. The "ant" moves according to the rules below:

  • At a white square, turn 90° clockwise, flip the color of the square, move forward one unit

All finite initial configurations tested eventually converge to the same repetitive pattern, suggesting that the "highway" is an attractor of Langton's ant, but no one has been able to prove that this is true for all such initial configurations. It is only known that the ant's trajectory is always unbounded regardless of the initial configuration – this is known as the Cohen–Kong theorem.

测试的所有有限初始构型最终都会收敛到相同的重复模式，表明“高速公路”是朗顿蚂蚁的吸引子，但是没有人能够证明这对所有这样的初始构型都是正确的。我们只知道蚂蚁的轨迹总是无界的，不管初始配置如何——这就是著名的 Cohen-Kong 定理。

  • At a black square, turn 90° counter-clockwise, flip the color of the square, move forward one unit


Langton's ant can also be described as a cellular automaton, where the grid is colored black or white and the "ant" square has one of eight different colors assigned to encode the combination of black/white state and the current direction of motion of the ant.[2]


In 2000, Gajardo et al. showed a construction that calculates any boolean circuit using the trajectory of a single instance of Langton's ant. Additionally, it would be possible to simulate an arbitrary Turing machine using the ant's trajectory for computation. This means that the ant is capable of universal computation.

2000年，Gajardo et al. 。展示了一个结构，计算任何布尔电路使用的轨迹，一个单一的实例朗顿的蚂蚁。此外，还可以使用蚂蚁的轨迹来模拟任意的图灵机进行计算。这意味着蚂蚁能够进行通用计算。

Modes of behavior

These simple rules lead to complex behavior. Three distinct modes of behavior are apparent,[3] when starting on a completely white grid.


  1. Simplicity. During the first few hundred moves it creates very simple patterns which are often symmetric.

Greg Turk and Jim Propp considered a simple extension to Langton's ant where instead of just two colors, more colors are used. The colors are modified in a cyclic fashion. A simple naming scheme is used: for each of the successive colors, a letter "L" or "R" is used to indicate whether a left or right turn should be taken. Langton's ant has the name "RL" in this naming scheme.

格雷格 · 特克和吉姆 · 普罗普认为这是兰顿蚂蚁的一个简单扩展，他们使用了更多的颜色，而不仅仅是两种颜色。颜色以循环方式进行修改。使用了一个简单的命名方案: 对于每个连续的颜色，用一个字母“ l”或“ r”来表示是否应该左转或右转。在这个命名方案中，兰顿的蚂蚁被命名为“ RL”。

  1. Chaos. After a few hundred moves, a large, irregular pattern of black and white squares appears. The ant traces a pseudo-random path until around 10,000 steps.
  1. Emergent order. Finally the ant starts building a recurrent "highway" pattern of 104 steps that repeats indefinitely.

Some of these extended Langton's ants produce patterns that become symmetric over and over again. One of the simplest examples is the ant "RLLR". One sufficient condition for this to happen is that the ant's name, seen as a cyclic list, consists of consecutive pairs of identical letters "LL" or "RR". (the term "cyclic list" indicates that the last letter may pair with the first one) The proof involves Truchet tiles.

这些扩展的朗顿蚂蚁中的一些会产生反复对称的模式。最简单的例子之一是蚂蚁“ RLLR”。这种情况发生的一个充分条件是，蚂蚁的名字被看作是一个循环列表，由连续的相同字母“ LL”或“ RR”组成。(术语“循环列表”表明，最后一个字母可以与第一个字母对)证明涉及 Truchet 瓦片。


All finite initial configurations tested eventually converge to the same repetitive pattern, suggesting that the "highway" is an attractor of Langton's ant, but no one has been able to prove that this is true for all such initial configurations. It is only known that the ant's trajectory is always unbounded regardless of the initial configuration[4] – this is known as the Cohen–Kong theorem.[5]

  • Some example patterns in the multiple-color extension of Langton's ants:
  • LangtonsAnt-nColor RLR 13937.png

    RLR: Grows chaotically. It is not known whether this ant ever produces a highway.

  • 图片: LangtonsAnt-nColor RLR 13937. png

    RLR: 生长混乱。现在还不知道这种蚂蚁是否建造过高速公路。

  • ==Universality==
  • LangtonsAnt-nColor LLRR 123157.png

    LLRR: Grows symmetrically.

  • 图片: LangtonsAnt-nColor LLRR 123157. png

    LLRR: 对称生长。

  • LangtonsAnt-nColor LRRRRRLLR 70273.png

    LRRRRRLLR: Fills space in a square around itself.

  • 图片来源: LangtonsAnt-nColor lrrrllr 70273. png

    lrrrrllr: 在自身周围的正方形中填充空间。

  • LangtonsAnt-nColor LLRRRLRLRLLR 36437.png

    LLRRRLRLRLLR: Creates a convoluted highway.

  • 图片: LangtonsAnt-nColor llrlrllr 36437. png

    llrrrlrllr: 建立一条曲折的高速公路。

  • LangtonsAnt-nColor RRLLLRLLLRRR 32734.png

    RRLLLRLLLRRR: Creates a filled triangle shape that grows and moves.

  • 图片: LangtonsAnt-nColor rlllrlrrrrr32734. png

    rlllrlrlrrrrrr: 创建一个填充的三角形形状，该形状可以生长和移动。

  • ==Extension to multiple colors==
  • CA3061-81k7.png

    L2NNL1L2L1: Hexagonal grid, grows circularly.

  • 图片: CA3061-81k7. png

    L2NNL1L2L1: 六边形网格，循环生长。

  • CA174906.png

    L1L2NUL2L1R2: Hexagonal grid, spiral growth.

  • 图片: ca174906. png

    L1L2NUL2L1R2: 六边形网格，螺旋生长。

  • CA50338 animation.gif

    R1R2NUR2R1L2: Animation.

  • 图片来源: CA50338 Animation.gif

    R1R2NUR2R1L2: Animation。

</gallery >

Some of these extended Langton's ants produce patterns that become symmetric over and over again. One of the simplest examples is the ant "RLLR". One sufficient condition for this to happen is that the ant's name, seen as a cyclic list, consists of consecutive pairs of identical letters "LL" or "RR". (the term "cyclic list" indicates that the last letter may pair with the first one) The proof involves Truchet tiles.


The hexagonal grid permits up to six different rotations, which are notated here as N (no change), R1 (60° clockwise), R2 (120° clockwise), U (180°), L2 (120° counter-clockwise), L1 (60° counter-clockwise).

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

  • Some example patterns in the multiple-color extension of Langton's ants:
  • LangtonsAnt-nColor RLR 13937.png

    RLR: Grows chaotically. It is not known whether this ant ever produces a highway.

  • LangtonsAnt-nColor LLRR 123157.png

    LLRR: Grows symmetrically.

  • LangtonsAnt-nColor LRRRRRLLR 70273.png

    LRRRRRLLR: Fills space in a square around itself.

  • LangtonsAnt-nColor LLRRRLRLRLLR 36437.png

    LLRRRLRLRLLR: Creates a convoluted highway.

  • LangtonsAnt-nColor RRLLLRLLLRRR 32734.png

    RRLLLRLLLRRR: Creates a filled triangle shape that grows and moves.

  • “一些例子的白蚁: ”
  • CA3061-81k7.png

    L2NNL1L2L1: Hexagonal grid, grows circularly.

  • Turmite-111180121010-12536.png

    Spiral growth.

  • Turmite-111180121010-12536. png

    螺旋增长。

  • CA174906.png

    L1L2NUL2L1R2: Hexagonal grid, spiral growth.

  • Turmite-120121010011-8342.png

    Semi-chaotic growth.

  • Turmite-120121010011-8342. png

    Semi-chaotic growth。

  • CA50338 animation.gif

    R1R2NUR2R1L2: Animation.

  • Turmite-121021110111-27731.png

    Production of a highway after a period of chaotic growth.

  • Turmite-121021110111-27731. png

    生产后的一段高速公路混乱成长期。

File:Turmite-121181121020-65932.png|Chaotic growth with a distinctive texture.

档案: Turmite-121181121020-65932. png | 混乱的生长和独特的纹理。


File:Turmite-180121020081-223577.png|Growth with a distinctive texture inside an expanding frame.

档案: Turmite-180121020081-223577. png | 生长与一个扩展框架内独特的纹理。

The hexagonal grid permits up to six different rotations, which are notated here as N (no change), R1 (60° clockwise), R2 (120° clockwise), U (180°), L2 (120° counter-clockwise), L1 (60° counter-clockwise).

File:Turmite-181181121010-10211.png|Constructing a Fibonacci spiral.

文件: Turmite-181181121010-10211. png | Constructing a Fibonacci spiral。


</gallery>

</gallery >

Extension to multiple states

Main article: Turmite

A further extension of Langton's ants is to consider multiple states of the Turing machine – as if the ant itself has a color that can change. These ants are called turmites, a contraction of "Turing machine termites". Common behaviours include the production of highways, chaotic growth and spiral growth.[6]

Multiple Langton's ants can co-exist on the 2D plane, and their interactions give rise to complex, higher-order automata that collectively build a wide variety of organized structures. There is no need for conflict resolution, as every ant sitting on the same square wants to make the same change to the tape. There is a YouTube video showing these multiple ant interactions.

多个朗顿蚂蚁可以在二维平面上共存，它们之间的相互作用产生了复杂的、高阶的自动机，这些自动机共同构建了各种各样的有组织结构。没有必要解决冲突，因为每一只坐在同一个方块上的蚂蚁都想对磁带做同样的改变。有一段 https://www.YouTube.com/watch?v=w6xqqhcgq5c 的 YouTube 视频展示了这些蚂蚁之间的多重互动。


  • Some example turmites:
  • Multiple turmites can co-exist on the 2D plane as long as there is a rule for what happens when they meet. Ed Pegg, Jr. considered ants that can turn for example both left and right, splitting in two and annihilating each other when they meet.
  • 只要有一个规则来规定它们相遇时会发生什么，多只白蚁就可以在2D 平面上共存。小埃德 · 佩吉认为蚂蚁可以同时转向左和右，分裂成两半并在相遇时消灭对方。
  • Turmite-111180121010-12536.png

    Spiral growth.

  • Turmite-120121010011-8342.png

    Semi-chaotic growth.

  • Turmite-121021110111-27731.png

    Production of a highway after a period of chaotic growth.

  • Turmite-121181121020-65932.png

    Chaotic growth with a distinctive texture.

  • Turmite-180121020081-223577.png

    Growth with a distinctive texture inside an expanding frame.

  • Turmite-181181121010-10211.png

    Constructing a Fibonacci spiral.


Extension to multiple ants

Multiple Langton's ants can co-exist on the 2D plane, and their interactions give rise to complex, higher-order automata that collectively build a wide variety of organized structures. There is no need for conflict resolution, as every ant sitting on the same square wants to make the same change to the tape. There is a YouTube video showing these multiple ant interactions.


Multiple turmites can co-exist on the 2D plane as long as there is a rule for what happens when they meet. Ed Pegg, Jr. considered ants that can turn for example both left and right, splitting in two and annihilating each other when they meet.[7]


See also


References

  1. ↑ Langton, Chris G. (1986). "Studying artificial life with cellular automata" (PDF). Physica D: Nonlinear Phenomena. 22 (1–3): 120–149. Bibcode:1986PhyD...22..120L. doi:10.1016/0167-2789(86)90237-X. hdl:2027.42/26022.
  2. ↑ 2.0 2.1 引用错误：无效<ref>标签；未给name属性为Gajardo2000的引用提供文字
  3. ↑ Pratchett, Terry (1999). The Science Of Discworld. 
  4. ↑ Bunimovich, Leonid A.; Troubetzkoy, Serge E. (1992). "Recurrence properties of Lorentz lattice gas cellular automata". Journal of Statistical Physics. 67 (1–2): 289–302. Bibcode:1992JSP....67..289B. doi:10.1007/BF01049035. S2CID 121346477.
  5. ↑ Stewart, I. (1994). "The Ultimate in Anty-Particles" (PDF). Sci. Am. 271 (1): 104–107. Bibcode:1994SciAm.271a.104S. doi:10.1038/scientificamerican0794-104. Archived from the original (PDF) on 3 March 2016. Retrieved 6 May 2013.
  6. ↑ 模板:Cite document.
  7. ↑ Pegg, Jr., Ed. "Math Puzzle". Retrieved 15 October 2009..


External links

模板:Commons category multi

Category:Artificial life

类别: 人工生命

Category:Cellular automaton rules

分类: 细胞自动机规则

Category:Turing machine

类别: 图灵机


This page was moved from wikipedia:en:Langton's ant. Its edit history can be viewed at 朗顿蚂蚁/edithistory

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