生命遊戲：細胞自動機的例子。
細胞自動機（英語：Cellular automaton），又稱格狀自動機、元胞自動機，是一種離散模型，在可計算性理論、數學及理論生物學都有相關研究。它是由無限個有規律、堅硬的方格組成，每格均處於一種有限狀態。整個格網可以是任何有限維的，同時也是離散的。每格於t時的態由t-1時的一集有限格（這集叫那格的鄰域）的態決定。每一格的「鄰居」都是已被固定的。（一格可以是自己的鄰居。）每次演進時，每格均遵從同一規矩一齊演進。
就形式而言，細胞自動機有三個特徵：
- 平行計算（parallel computation）：每一個細胞個體都同時同步的改變
- 局部的（local）：細胞的狀態變化只受周遭細胞的影響。
- 一致性的（homogeneous）：所有細胞均受同樣的規則所支配
構成
一個標準的細胞自動機（A）由元胞、元胞狀態、鄰域和狀態更新規則構成。用數學表示為： A = ( L , d , S , N , f )
其中L為元胞空間；d為元胞自動機內元胞空間的維數；S是元胞有限的、離散的狀態集合；N為某個鄰域內所有元胞的集合；f為局部映射或局部規則。 元胞空間是元胞所分布的空間網點的集合。理論上元胞空間在各個維向上是無限延伸的，為了能夠在計算機上實現，而定義了邊界條件，包括周期型、反射型和定值型。 一個元胞通常在一個時刻只有取自一個有限集合的一種狀態，例如 {0,1}。元胞狀態可以代表個體的態度，特徵，行為等。在空間上與元胞相鄰的細胞稱為鄰元，所有鄰元組成鄰域。
歷史
細胞自動機最早由美籍數學家馮·諾依曼（John von Neumann）在1950年代為模擬生物細胞的自我複製而提出，但是並未受到學術界重視。直到1970年，英國數學家約翰·何頓·康威（John Horton Conway）設計了生命遊戲並經馬丁·葛登在《科學美國人》雜誌上介紹，才吸引了科學家們的注意。此後，英國學者史蒂芬·沃爾夫勒姆（Stephen Wolfram）對初等元胞機256種規則所產生的模型進行了深入研究，並用熵來描述其演化行為，將細胞自動機分為平穩型、周期型、混沌型和複雜型。
分類
史蒂芬·沃爾夫勒姆在《一種新科學》和幾篇從80年代中期開始的論文中定義了四類細胞自動機和其他幾個簡單的計算模型。元胞自動機的早期研究往往試圖確定具體規則的模式類型，他提出的分類是對規則本身分類的第一次嘗試。按照複雜性分類的秩序：
- 1類：幾乎所有的初始模式迅速演變成一個穩定的，均勻的狀態。在初始模式的任何隨機性會消失。
- 2類：幾乎所有的初始模式迅速演化為穩定或振盪結構。一些在初始模式的隨機性可能會被過濾掉，但是還有一些保留。在初始模式的局部變化傾向於繼續保持局部性。
- 3類：幾乎所有的初始形態將會演變成一個偽隨機或混沌的形式。任何穩定的結構很快會被周圍的噪音破壞，在初始模式的局部變化有無限蔓延的傾向。
- 4類：幾乎所有的初始模式將會演變成相互作用的複雜和有趣的方式結構，並且局部結構的形成能夠長時間存在。2類的穩定或振盪的結構可能是最終的結果，但需要達到這個狀態的步驟數目可能是非常大的，即使在初始模式比較簡單的情況下。初始模式的局部變化可能會無限蔓延。史蒂芬·沃爾夫勒姆推測不是所有的4類細胞自動機都能夠進行通用計算。這已經在規則110和約翰·何頓·康威的生命遊戲中被證明。
根據史蒂芬·沃爾夫勒姆的說法，這些定義在本質上是定性的但是任有解釋一些空間。
「……幾乎任何一般的分類方案都有不可避免的情況，比如說根據不同的定義會被分配到不同的類裡。因此細胞自動機也是這樣：偶爾有規則……顯示不同類的一些特點。」
他的分類已經與一個類具有壓縮長度輸出的元胞自動機相匹配。 已經有人在嘗試進行細胞自動機的正式嚴格分類，是根據史蒂芬·沃爾夫勒姆的分類做區分，例如，Culik和Yu提出三種定義的類（並且第四個和它們不同），有時被稱為Culik-Yu 類；能夠被分到這種類里的問題被證明是不可判定的。史蒂芬·沃爾夫勒姆的2類可劃分為穩定（定點）和振盪（周期）規則兩個小組。
國外相關研究
細胞自動機是一種非常簡單的計算形式，它的起源很難確定，但早在20世紀50年代初，洛斯阿拉莫斯的數學家斯坦尼斯勞·烏蘭姆就用第一台數字計算機來處理過隨時間演化的圖案。他稱之為「遞歸定義的幾何學」。 第一個真正的細胞自動機可能是由烏蘭姆的密友，著名的數學家和計算機科學家約翰尼·馮·諾依曼發明的。烏蘭姆建議馮·諾依曼嘗試在人工宇宙中構建基於規則的機器，這有助於模擬自我複製。馮·諾依曼選擇了一個棋盤宇宙，其中每個方塊代表一個遵守一套規則的細胞，這就是第一個細胞自動機。
細胞自動機是一種非常簡單的計算形式。當你觀察周圍的世界時，你所看到的事物是處於一定的位置和狀態的。生物細胞位於其他細胞叢中的特定位置，其狀態要麼是活著的，要麼是死亡的。你可以想出其他非生物學的例子，但正是這一生物學例子真正推動了細胞自動機的誕生。 假設我們有一個細胞，它有特定的位置和狀態。 在大多數情況下，你會假設細胞的狀態受其周圍細胞的影響。然而重點是在沒有細胞的幾英里外發生了什麼，這是一種局部化假設，也是大多數經典物理學固有的假設。例如，波是由一個微分方程描述的，此微分方程將一個點上發生的事情與該點周圍無窮小的區域中發生的事情聯繫起來。 你或許會認為局部假設過於嚴格，因為它不允許遠程交互，但在物理世界中，遠程交互是通過點對點移動的影響而產生的，遠程交互是通過只依賴於局部相互作用的脈衝和波的傳播產生的。 我們最終假設影響細胞自動機的因素是環境。假設細胞的狀態僅受當地環境的影響。然而在大多數情況下，我們會將假設範圍縮到更小，認為細胞的狀態只受其當前狀態和相鄰細胞狀態的影響。
根據此想法，假設最開始你有一個初始的細胞群，且每個細胞都有一個初始狀態，然後你讓這個細胞群進行分裂。此操作通常要在幾段不同時間內完成，你也可以在連續時間內運行細胞自動機，但這樣操作起來難度更大。 當時間為t時，你獲得了所有細胞的位置和狀態；然後運用規則，根據每個細胞的當前狀態和相鄰細胞的狀態推測出此細胞的狀態。當時間為t+1時，所有細胞都能按照相同的規則改變其狀態。 要明確定義細胞自動機，必須確定細胞可能的狀態、細胞的初始排列情況和更新規則。 你可以將細胞自動機視為用於描述許多物理現象的經典微分方程的數字版本。但是，細胞自動機並不像你認為的那樣容易分析。典型的細胞自動機中使用的規則的性質使得我們很難預測在任意給定的初始條件下細胞將發生什麼變化。 例如，你可能會問，給定的一組細胞是否會振盪、消失或無約束地生長，但很難得出問題的答案。細胞自動機之所以吸引人，是因為它們不可預測，而且大多無法測量。 細胞自動機是本地規則如何影響全局組織行為的例子，或者至少是看起來像全局組織行為的例子。
能夠識別輪廓的細胞自動機
這裡可以使用一個矩形網狀細胞群作為執行某些有用操作的細胞自動機示例，其中每個細胞都為黑色或白色並處於初始設置狀態： 每個細胞在下一個步驟都將遵守如下規則： 如果一個細胞為黑色，與之相鄰的細胞為白色，那麼此細胞將保持黑色，反之，細胞將變為白色。
這裡，相鄰細胞指的是水平或垂直相鄰的任何細胞。 此規則僅將原始形狀的輪廓保留為黑色：
換句話說，此規則成功地篩選出了形狀的輪廓。請注意，任何細胞都只使用了本地信息，但卻成功地提取了我們可能認為是全局的東西，即輪廓。 這種現象與在體育賽事中人群中的成員被要求在特定時間舉起帶有不同的圖片和圖案的卡片的情況相同。 應用本地規則可以產生全局模式。
約翰康威的細胞自動機Life
這個例子非常簡單且深入人心，對於細胞自動機來說非常容易理解。在所有細胞自動機中，最著名的是康威的生命遊戲（Conway's Life），這看起來同樣很簡單，但是科學家花了很長時間才弄清楚它的工作方式，而且目前還在繼續探尋中。 此細胞自動機是由劍橋數學家約翰·霍頓·康威（John Horton Conway）於1970年設計的，並在馬丁·加德納（Martin Gardner）的《科學美國人》專欄（1970年10月和1971年2月）公開了此設計。
Life中的規則很簡單。即宇宙是一個矩形網格，每個網格方格代表一個細胞，它可以是活的也可以是死的。 每個細胞顯然有八個相鄰細胞，每一代細胞的情況取決於與之相鄰細胞的數目：
N Next generation2 No change3 Alive or On0,1,4-8 Dead or off
請注意，此規則非常簡單。想像如果你是一個巨大矩形細胞中間的細胞，你就知道你該做什麼了。你只需計算與你相鄰的八個細胞中有多少是活著的，如果結果為3，則將你的狀態設置為「開啟」（無論當前你是開啟還是關閉狀態）。如果計算結果正好是2，那麼你將不對當前狀態進行更改，而對於任何其他值，你都需要把狀態設置為「關閉」。 可以看到，Life是一個完全局部的過程，因為沒有一個細胞知道它周圍的全局情況。或許認為Life非常無聊，因為在裡面不太可能發生大規模的結構變化，但這個想法是錯的。 例如，試著預測一行細胞會發生什麼變化，先看一個細胞，然後兩個，然後三個，以此類推。 剛開始只有一個細胞死亡。
又有兩個細胞在第一步死亡了，然而，這三個細胞發生了顯著的變化，給出了第一個提示，表示這裡正在發生很多事情。水平排列的三個細胞在下一代中變為垂直排列的細胞，然後又變回水平排列的三個細胞。振盪器就這樣產生了！ 四個細胞組成一個實心塊，然後變成一個有孔的塊，這個孔是穩定且不變的。 五個細胞經歷一系列變化後會產生一組四個3細胞振盪器。 六個細胞經歷一系列有趣的形狀變化後消失了。 到現在為止，你可能已經明白了其中的規則。 Life是不可預測的。
了解glider
事實上，Life讓人難以理解，即使是關於它簡單的問題我們也很難回答。例如，是否存在能夠無窮無盡地增長的模式？1969年，康威發現了一種由五個細胞組成的有趣的小模式，他稱之為滑翔機（glider）。
有趣的是，滑翔機在穿過Life時，它表現得像一個可以用來建造其他形狀的基本粒子一樣。 然而，真正的突破是在1970年，當時，為了贏得50美元的獎金，比爾·戈斯珀發現了滑翔機槍。 這種排列複雜的細胞每30代就會發射一次新的滑翔機。最後，實驗證明有些模式可以無限制地增長，因為滑翔槍每隔30代增加五個細胞。 然而，更重要的是，有了滑翔機槍，你就可以開始在Life中製造機器了！ 滑翔機的氣流可以像電流一樣使用，因此可以被用來建立邏輯門和存儲器。很快，一台完整的生命計算機就被建造出來了，證明了僅涉及每個細胞局部行為的簡單規則產生了像數字計算機一樣複雜的東西。換句話說，它相當於一個通用圖靈機，可以計算任何可以被計算的東西。
繼滑翔機槍之後，人們陸續發現了各種有趣的東西，振盪器、移動器、發射器等等。 最重要的是，即使在今天，關於Life的實驗仍然還在進行；這些實驗很少得到理論上的驗證，即使有，也是極少數的。更重要的是，Life只是一系列類似的細胞自動機的一個例子，每一個細胞自動機都是一個簡單規則的集合，它們總能導致複雜的行為。 通常，細胞自動機是一個細胞的世界，每個細胞可以處於多個狀態中的一種，並且添加了一組僅依賴於相鄰細胞的規則。 鑑於這些細胞自動機是小型人造宇宙，你可以看到我們並不能對它們進行很好的解釋。在我們自己製造的宇宙中，我們推測每件事都可能建立在一些簡單的規則之上，這些規則產生了所有的複雜行為，因此我們會去尋找大的統一理論或任何事物都適用的理論。如果我們在知道規則的情況下卻找不到一個通用理論，那麼結果就不盡人意了。 世界上有很多2D細胞自動機，實際上，Life只是一組名為「Totalistic」的細胞自動機的一個例子。在全局細胞自動機中，細胞相當於一個整數，數值僅取決於其相鄰細胞的狀態和其可能出現的當前狀態的總和。
一維
如上面描述的Life一樣，二維細胞自動機太複雜，因而無法詳細分析。 數學家史蒂芬·沃爾夫拉姆提出了解決方案，他對該理論的第一個重要貢獻是將情況降低到可以分析的程度。他認為一維細胞自動機值得研究。 一維細胞自動機的概念與二維細胞自動機沒有什麼不同，但是當我們從一行細胞開始，在下一個標有記號的地方時，該行就會被一個遵循一定規則的新行替換。 因為這只是一個一維圖，因此我們實際上不需要替換現有的行，只需在其下面顯示新行，建立一個完整的細胞自動機開發模式。我們還可以根據細胞的顏色、與之相鄰的其他兩個細胞以及它下面新細胞的顏色來指定規則。 例如，模式：
指定一個規則，如果某個細胞為白色且與之相鄰的細胞中有兩個為黑色，則此細胞下面的細胞也應為黑色。 由於相鄰細胞只有八種可能的情況，我們只需要列出八個中每一個細胞是黑色還是白色，一個完整的規則就可以確定在任何情況下細胞可能出現的情況。 通過將黑色設為1，白色設為0，你可以為每個相鄰模式標記從0到7之間的數字，然後將下一行的黑色或白色細胞看作八個0或八個1讀取，即二進位數。 這可以用作指定規則的索引。
這意味著你可以按編號引用一維細胞自動機中可能的256條規則中的任何一條。 這本身就是一個概念上的突破，因為現在你可以對每條可能規則的行為進行分類。 這正是生物學家在遇到新生物圈時會做的事情。一旦你對所看到的內容進行分類，你就可以掌握其中的模式並對看到的內容進行理論分析。 如果你沒有對其進行分類，無論它有多麼有趣，你看到的只是一個沒有任何差別的混亂行為。 沃爾夫拉姆通過模擬這些行為來檢查所有256條規則，並發現有四類行為。
- 第一類行為很無聊，只會導致打開或關閉狀態。
- 第二類行為也相當無聊，此類行為會導致穩定狀態，比第一類稍微有趣一點。
- 第三類行為是無序行為，隨機三角形和「視頻噪聲」。
- 第四類行為產生包含「類似Life」模式的複雜行為。第四類行為表明，即使是一維細胞自動機也有足夠的複雜性來產生有趣的行為。
在這些一維細胞自動機中，很多都產生了有趣的模式，這些模式玩起來也很有趣。從圖形的角度看，這些模式或許沒有分形圖那樣令人印象深刻，但考慮到投入的數量，似乎還是有所收穫，這也是最重要的一點。 即使是一維細胞自動機也足夠複雜，使你相信簡單中也能產生複雜的事物。實際上，規則30被提議作為一種加密方法。單向函數只是初始狀態演化而來的，由於很難從最終配置反向工作到創建它的初始配置，因此信息不能被破解。
廣義細胞自動機
你可以創建自己的細胞自動機類型，你可以改變網格的形式、細胞的狀態以及應用的規則。如果你願意的話，你也可以在2D以上的空間工作，但事實證明這比你想像的要困難得多。 同樣令人感興趣的是概率細胞自動機，其中的更新規則指定狀態更改的概率。 有一類重要的細胞自動機是可逆的。如果初始配置和最終配置之間存在一對一的對應關係，那麼在某種意義上，這樣的細胞自動機是不可逆的，通常用於物理系統建模。可逆系統遵循熱力學第二定律，既不產生也不破壞信息。並不是所有的細胞自動機都是可逆的，而且許多細胞自動機只能保持在最初狀態，然而，這類情況很難得到證明。 今天人們對細胞自動機的研究範圍非常廣泛，包括在Life中尋找有趣事物的新配置、尋找具有特定物理屬性的3D細胞自動機，以及使用遺傳算法培育細胞自動機。 也許最重要的是細胞自動機是分布式並行處理模型，可能比map / reduce和Hadoop使用起來更方便。如果你覺得這一點令人驚訝，請認清一個事實，即電子表格是可編程細胞自動機，其中每個單元格都有自己的規則。具有固定規則的細胞自動機是單指令多數據（SIMD）並行性的模型，具有可變規則的細胞自動機是多指令多數據（MIMD）並行性的模型。
後記
早在1950年代就已經開啟了模擬宇宙和生命演化的研究，而且很驚人的發現在那個電腦不發達的年代已經可以成功創造電子式演化模型，到了1980年代更有科學家用這個簡單的程式成功模擬出宇宙演化的過程，我們回頭看看人類的科技發展，自1850年後科技就突飛猛進，各式理論和發現不斷出世，一百年後1950年已經可以用簡單的程式模擬生命的演化，30年後的1980年代已經用同一套程式模擬出宇宙原型，到了今年2024年，已經又過了40年，你覺得人類還創造不出來一個虛擬宇宙嗎？
還記不記得馬斯克說過一句話：
我們活在真實世界的概率只有十億分之一
人類第一台電腦誕生於1942年，自從有了電腦之後，只用了短短40年就模擬出宇宙規律，現在經過80年了，也許早就有一個虛擬宇宙在某個隱密實驗室裡運作，更何況在我們地球之外的高等智慧文明，他們的科技領先人類上萬年，或許我們這個宇宙就是一個虛擬世界，你我都是由0和1所組成的虛擬人物，只是各自的靈魂在這個虛擬世界創造了一個身份來體驗人生而已，而那些神話傳說裡的神，也許只是這個虛擬世界的管理者GM，試想一下，你玩的電腦遊戲或是手遊，遊戲管理員GM是不是就如同神一般的存在，因為他們只要寫一段代碼，什麼都可以實現，而代碼就是神話傳說裡的咒語，又或者是天使的語言。
耶穌看著他們說：「在人是不能，在神卻不然，因為神凡事都能。」 – 馬可福音 10:27
最後回憶：以前我玩某款遊戲當GM，玩家四十個人殺BOSS打了半小時，我一個人一刀直接秒BOSS。
（部分內容參考於網路資訊）
