蘭頓螞蟻是由克里斯托夫·蘭頓提出的細胞自動機的例子。
基本介紹
- 中文名：蘭頓螞蟻
- 外文名：Langton's ant
- 提出者：克里斯托夫·蘭頓
- 簡介：細胞自動機
簡介,由來：,釋義：,規則,行為模式,推廣,
簡介
由來：
蘭頓螞蟻（英語：Langton's ant）是細胞自動機的例子。它由克里斯托夫·蘭頓在1986年提出，它由黑白格子和一隻“螞蟻”構成，是一個二維圖靈機。蘭頓螞蟻擁有非常簡單的邏輯和複雜的表現。在2000年蘭頓螞蟻的圖靈完備性被證明。蘭頓螞蟻的想法後來被推廣，比如使用多種顏色。
釋義：
在平面上的正方形格被填上黑色或白色。在其中一格正方形有一隻“螞蟻”。它的頭部朝向上下左右其中一方。
若螞蟻在黑格，右轉90度，將該格改為白格，向前移一步；
若螞蟻在白格，左轉90度，將該格改為黑格，向前移一步。
很多時，螞蟻剛剛開始時留下的路線都會有接近對稱、像是會重複。但不論起始狀態如何，螞蟻的路線必然是無限長的。
規則
在平面上的正方形格被填上黑色或白色。在其中一格正方形有一隻“螞蟻”。它的頭部朝向上下左右其中一方。
- 若螞蟻在白格，右轉90度，將該格改為黑格，向前移一步；
- 若螞蟻在黑格，左轉90度，將該格改為白格，向前移一步。
行為模式
若從全白的背景開始，在一開始的數百步，螞蟻留下的路線會出現許多對稱或重複的形狀，然後會出現類似混沌的假隨機，至約一萬步後會出現以104步為周期無限重複的“高速公路”朝固定方向移動。在目前試過的所有起始狀態，螞蟻的路線最終都會變成高速公路，但尚無法證明這是無論任何起始狀態都會導致的必然結果。
推廣
除了兩種顏色分別讓螞蟻左轉或右轉，也可以定義更多種顏色進行循環。通用的表示方法是用L和R依序表示各顏色是左轉還是右轉，蘭頓螞蟻的規則即可表示為RL。有些規則會產生對稱或重複的形狀。另外除了用方格，也可以用其他如六角形的格子。
