2026-08-28·作者 Sijie Wang#idea#math

langtons-ant

兰顿蚂蚁(与 turmites)

父级:famous-machines

一台几乎没有规则的二维图灵机,因从混沌中涌现出秩序而著名。

规则。 一只"蚂蚁"停在一个由黑白方格组成的网格上:

  • 停在白色格子上:向右转 90°,把该格翻成黑色,向前一步;
  • 停在黑色格子上:向左转 90°,把该格翻成白色,向前一步。

行为。 从一张空白网格出发,蚂蚁的轨迹在大约一万步之内看起来完全混沌,随后——出人意料地——收敛成一条周期性的"高速公路":一个不断自我重复的 104 步图案,径直朝无穷远处推进,永不停止。至今没有人给出过简单的证明来解释这条高速公路为何必然出现;这是一个只能靠亲手跑一遍才能得知、无法提前预测的秩序的典型例子(参见一般情形下不可计算的行为)。

它是通用的。 只要选取合适的初始格子配置,就能用蚂蚁的路径搭出逻辑门和导线,因此兰顿蚂蚁是图灵完备的——两行规则就撑起了完整的计算能力。turmites 把它推广到更多的状态/颜色,以及任意的转向表,是一台名副其实的二维读写移动机器。

关于这一条

sijie 的一条 wiki 条目。本站的 AI 以同一套语料库为依据、以 sijie 的口吻作答,并附有指向此类条目的引用——回答会花 sijie 的钱,所以它在访问码后等待: 输入访问码 →