蘭頓螞蟻

蘭頓螞蟻（英語：Langton's ant）是細胞自動機的例子。它由克里斯托夫·蘭頓在1986年提出，它由黑白格子和一隻「螞蟻」構成^[1]，是一個二維圖靈機。蘭頓螞蟻擁有非常簡單的邏輯和複雜的表現。在2000年蘭頓螞蟻的圖靈完備性被證明。蘭頓螞蟻的想法後來被推廣，比如使用多種顏色。

規則

在平面上的正方形格被填上黑色或白色。在其中一格正方形有一隻「螞蟻」。它的頭部朝向上下左右其中一方。

若螞蟻在白格，右轉90度，將該格改為黑格，向前移一步；
若螞蟻在黑格，左轉90度，將該格改為白格，向前移一步。

行為模式

若從全白的背景開始，在一開始的數百步，螞蟻留下的路線會出現許多對稱或重複的形狀，然後會出現類似混沌的假隨機，至約一萬步後會出現以104步為周期無限重複的「高速公路」朝固定方向移動^[2]。在目前試過的所有起始狀態，螞蟻的路線最終都會變成高速公路，但尚無法證明這是無論任何起始狀態都會導致的必然結果^[3]。

推廣

除了兩種顏色分別讓螞蟻左轉或右轉，也可以定義更多種顏色進行循環。通用的表示方法是用L和R依序表示各顏色是左轉還是右轉，蘭頓螞蟻的規則即可表示為RL。有些規則會產生對稱或重複的形狀。另外除了用方格，也可以用其他如六角形的格子。

使用多種顏色的蘭頓螞蟻的示例
RLR: 混沌的生長，沒有證實會產生高速公路
LLRR: 對稱的生長.
LRRRRRLLR: 形成方塊.
LLRRRLRLRLLR: 生成高速公路.
RRLLLRLLLRRR: 生成一個移動並生長的實心三角形.
L2NNL1L2L1: 六邊形循環生長.
L1L2NUL2L1R2: 六邊形螺旋生長.
R1R2NUR2R1L2: 動畫.

參考文獻

^ Langton, Chris G. Studying artificial life with cellular automata. Physica D: Nonlinear Phenomena. 1986, 22 (1-3): 120–149. doi:10.1016/0167-2789(86)90237-X.
^ Pratchett, Terry. The Science Of Discworld. 1999.
^ Bunimovich, Leonid A.; Troubetzkoy, Serge E. Recurrence properties of Lorentz lattice gas cellular automata. Journal of Statistical Physics. 1992, 67 (1-2): 289–302. doi:10.1007/BF01049035.

外部連結

參見

生命遊戲

[1] Langton, Chris G. Studying artificial life with cellular automata. Physica D: Nonlinear Phenomena. 1986, 22 (1-3): 120–149. doi:10.1016/0167-2789(86)90237-X.

[2] Pratchett, Terry. The Science Of Discworld. 1999.

[3] Bunimovich, Leonid A.; Troubetzkoy, Serge E. Recurrence properties of Lorentz lattice gas cellular automata. Journal of Statistical Physics. 1992, 67 (1-2): 289–302. doi:10.1007/BF01049035.

[1]

[2]

[3]