兰顿蚂蚁

一个四状态二维图灵机，于 20 世纪 80 年代发明。蚂蚁从包含黑色和白色单元格的网格开始，然后遵循以下规则。

1. 如果蚂蚁在黑色方格上，它向右转 并向前移动一个单位。

2. 如果蚂蚁在白色方格上，它向左转 并向前移动一个单位。

3. 当蚂蚁离开一个方格时，它会反转颜色。

当蚂蚁在空白网格上开始时，它最终会构建一条“高速公路”，这是一系列 104 个无限重复的步骤，每次将蚂蚁垂直和水平位移两个像素。上面的图表显示了蚂蚁从完全白色的网格开始，在 386 步（左图）和 (右图) 之后的情况。在右图中，高速公路正在向右下角构建。蚂蚁路径是无界的这一事实由 Cohen-Kung 定理保证。人们相信，无论蚂蚁从什么初始模式开始，它最终都会构建一条高速公路（尽管原则上可能需要很长时间才能达到这一点）。这似乎自然而然地源于兰顿蚂蚁是可逆的这一事实，尽管这仍然没有得到正式证明（Beermann 和 Van Foeken）。

2009 年，Benedetti 发布了一个关于多种行为的视频。