簡明介紹：http://mmdays.com/2007/07/12/game_of_life/ 簡單模擬：http://www.bitstorm.org/gameoflife/ 更多例子： 網址：http://www.atlas-zone.com/complex/alife/ca/index.html 細胞自動機　Cellular Automata 2002, 1, 10　吳文成 　　細胞自動機（Cellular Automata）最初由數學家 Stanislaw M. Ulam（1909-1984） 與 John von Neumann（1903-1957）於 1950 年代所提出 ，在型態表現上，細胞自動機 是一個離散型的動力系統（ Discrete Dynamical Systems）。在 1940 年代 ，von Neumann 與共事的科學家們合作設計了可儲存程式的數位電腦之後，他就對自我複製發生 興趣：能儲存程式的機器能不能自我複製 ？ von Neumann 認為，至少在原則上與形式上是可行的，於是他開始作這方面的理論研 究，過程中他提出了「細胞自動機」的概念， 這個實際構想是由羅沙拉摩斯的數學家 Ulam 所建議的 。當細胞自動機在電腦上模擬的時候，幾乎可以複製出類似於自然界當中實際發生的動力 系統運作，這使得細胞自動機成為了研究複雜系統行為的最初理論框架，羅沙拉摩斯的博 士後研究員 Christopher Langton 因而提出了「人工生命」（ Artificial Life ）這個 名詞 ， 細胞自動機便是人工生命的第一個雛形，並且變成複雜性科學，或者說是複雜適 應性系統的其中一支。 　　細胞自動機是由一些特定規則的格子所組成，每個格子看做是一個細胞；每一個細胞 可以具有一些狀態，但是在某一時刻只能處一種狀態之中。隨著時間的變化（我們稱作「 疊代」過程），格子上的每一個細胞根據周圍細胞的情形，按照相同的法則而改變狀態， 換句話說，一個細胞的狀態是由上一個時刻所圍繞的細胞的狀態所決定。以人工生命的角 度來看，細胞自動機可以視為一個讓許多單細胞生物生活的世界，在我們設定好這個世界 的初始狀態之後，它們便按照同一個規則做演化。 　　設計一個細胞自動機需要包含幾個部份： 　　◆ 決定細胞活動空間的維度 　　◆ 定義細胞可能具有的狀態 　　◆ 定義細胞改變狀態的規則 　　◆ 設定細胞自動機中各個細胞的初始狀態 　　細胞自動機，在細胞活動的空間上，可以是一維的，二維的，三維的，或更高維度， 在這個網頁，筆者要分別介紹二維的細胞自動機（也稱作「生命遊戲」），與一維的細胞 自動機。透過不同的設計，細胞自動機可以展現無限的多樣性，其中最讓人驚異的是有些 細胞自動機可以產生存在於大自然的景象，例如貝殼上的圖案、雪花的結構、蜿蜒的河流 等等，另外，我們也可以發現，這些小方格的變化似乎展現了許多真實生命的特質，例如 ，細胞自動機中的細胞們會像有機生物一般，有移動、成長、滅亡與自我複製等類似的行 為。 　　就形式而言，細胞自動機有三個特徵： 　　◆ 平行計算（parallel computation）：每一個細胞個體都同時同步的改變 　　◆ 局部的（local）：細胞的狀態變化只受周遭細胞的影響。 　　◆ 一致性的（homogeneous）：所有細胞均受同樣的規則所支配 　　事實上，有些研究學者更進一步猜測，我們存在的這個宇宙是否就是一種極其複雜的 細胞自動機，我們的宇宙的確與理論上的細胞自動機有很多相似的地方，像是上述的細胞 自動機之三個特徵，宇宙也都符合：宇宙是平行處理的，宇宙中的每一點受鄰近狀態的影 響最大，宇宙各處遵循著同樣的自然律。雖然與整個宇宙相比，細胞自動機的規則是過於 簡單，但是它裡面所蘊含的道理可能與宇宙的機制是相通的。 理論物理學家 Stephen Wolfram（1959-）就指出 ，細胞自動機的數學架構，與一些造成真實世界的複雜物理系 統之數學架構是完全一樣的，也許這正是掌管遺傳重任的 DNA 所賴以工作的原理 。當你 看到自然界那些貝殼或指紋曲折的圖案時，不免要問 ：「這麼複雜的圖案要如何編碼到 DNA 裡頭呢？」Wolfram 說 ：「如果我猜的不錯，那些圖形是由類似於細胞自動機的簡 單法則所產生的，而這樣的編碼顯然是易如反掌。」 　　細胞自動機以簡單的規則，卻能夠產生複雜的動態交互現象，顯然我們不該只是以一 個數學遊戲，來看待它。這些年來，細胞自動機已經被運用於不同領域的研究，包括通訊 、計算、建設、生長、再生、競爭及演化。細胞自動機已為物理中平常的微分方程式提供 極為簡單的模型，例如熱和波的波動方程，同時也為湍流、混沌、碎形等提供了離散型的 模型，最後，利用細胞自動機所做的生物模型也被提出。接下來，筆者將盡可能地介紹細 胞自動機的規則、範例與相關資訊，以下的介紹分為兩種不同類型的細胞自動機： 　　｜ 　　├─ 二維的細胞自動機： 　　｜　　　｜ 　　｜　　　├─ 生命遊戲，與其規則 　　｜　　　├─ 生命遊戲的有趣範例 　　｜　　　├─ 生命遊戲的規則變化（一） 　　｜　　　├─ 生命遊戲的規則變化（二） 　　｜　　　├─ 生命遊戲的規則變化（三） 　　｜　　　└─ 生命起源於混沌的邊緣 　　｜ 　　├─ 一維的細胞自動機： 　　｜　　　｜ 　　｜　　　├─ 一維細胞自動機，與其規則（一） 　　｜　　　├─ 一維細胞自動機，與其規則（二） 　　｜　　　├─ 一維細胞自動機，與其規則（三） 　　｜　　　├─ 一維細胞自動機的有趣範例 　　｜　　　└─ 四個普遍性等級的再探討 　　｜ 　　└─ 相關連結與資源 　　瞭解了細胞自動機的疊代過程之後，你會發現：細胞自動機在某一疊代的細胞形態只 會產生「唯一」形態的下一代，而我們卻無法從新一代的形態而回溯得知上一代確定的細 胞形態，因為這樣的「回溯」有太多種可能性，而且可能性的數量會隨著一次接著一次的 「回溯」而以指數比例地增加，這使得我們即使看見某一疊代中有趣的細胞演化，卻無法 準確地推回出它的初始狀態 。這種性質，我們稱呼為「Forward-Deterministic」，意思 是，細胞自動機的疊代演化是往前決定的，它有許多個可能的過去，但是它的未來發展只 有一個，而這個唯一的未來發展所產生的複雜度，卻常常在人們的預期與想像之外。 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.229.124.159