蘭頓螞蟻

一個四狀態二維圖靈機，於 20 世紀 80 年代發明。螞蟻從包含黑色和白色單元格的網格開始，然後遵循以下規則。

1. 如果螞蟻在黑色方格上，它向右轉 並向前移動一個單位。

2. 如果螞蟻在白色方格上，它向左轉 並向前移動一個單位。

3. 當螞蟻離開一個方格時，它會反轉顏色。

當螞蟻在空白網格上開始時，它最終會構建一條“高速公路”，這是一系列 104 個無限重複的步驟，每次將螞蟻垂直和水平位移兩個畫素。上面的圖表顯示了螞蟻從完全白色的網格開始，在 386 步（左圖）和 (右圖) 之後的情況。在右圖中，高速公路正在向右下角構建。螞蟻路徑是無界的這一事實由 Cohen-Kung 定理保證。人們相信，無論螞蟻從什麼初始模式開始，它最終都會構建一條高速公路（儘管原則上可能需要很長時間才能達到這一點）。這似乎自然而然地源於蘭頓螞蟻是可逆的這一事實，儘管這仍然沒有得到正式證明（Beermann 和 Van Foeken）。

2009 年，Benedetti 釋出了一個關於多種行為的影片。