兰顿蚂蚁(与 turmites)
一台几乎没有规则的二维图灵机,因从混沌中涌现出秩序而著名。
规则。 一只"蚂蚁"停在一个由黑白方格组成的网格上:
- 停在白色格子上:向右转 90°,把该格翻成黑色,向前一步;
- 停在黑色格子上:向左转 90°,把该格翻成白色,向前一步。
行为。 从一张空白网格出发,蚂蚁的轨迹在大约一万步之内看起来完全混沌,随后——出人意料地——收敛成一条周期性的"高速公路":一个不断自我重复的 104 步图案,径直朝无穷远处推进,永不停止。至今没有人给出过简单的证明来解释这条高速公路为何必然出现;这是一个只能靠亲手跑一遍才能得知、无法提前预测的秩序的典型例子(参见一般情形下不可计算的行为)。
它是通用的。 只要选取合适的初始格子配置,就能用蚂蚁的路径搭出逻辑门和导线,因此兰顿蚂蚁是图灵完备的——两行规则就撑起了完整的计算能力。turmites 把它推广到更多的状态/颜色,以及任意的转向表,是一台名副其实的二维读写移动机器。