細胞自動機 - iThome

而由英國數學家John Conway創造的生命遊戲，屬於細胞自動機（Cellular automaton）範疇，理論上，這樣的運算具有圖靈完備的能力，甚至可應用於許多科學 ... 移至主內容 文/林信良 | 2020-08-28發表 關於細胞自動機的研究，最早可追溯至1950年代，這篇文章想從生命遊戲（Gameoflife）開始談起，或許不少程式人也曾聽過或實作過這個簡單的遊戲。

而由英國數學家JohnConway創造的生命遊戲，屬於細胞自動機（Cellularautomaton）範疇，理論上，這樣的運算具有圖靈完備的能力，甚至可應用於許多科學領域。

Conway的生命遊戲 在1970年10月的《ScientificAmerican》的數學遊戲專欄中，JohnConway發表了生命遊戲，他建議你兩種顏色棋子要夠多，以及一個夠大的棋盤，棋盤中各方格的細胞與鄰居形成九宮格，也就是每個細胞的鄰居有八個，一開始各細胞會有個初始狀態：要不就活著，要不就死亡。

遊戲的規則是這樣的：如果細胞的鄰居為二個或三個，該細胞在下一代（generation）的狀態會是存活（穩定）。

若細胞的鄰居小於一個或在四個以上，下一代將會死亡（孤單死或擁擠死）。

死亡狀態的細胞若有三個存活狀態的鄰居，下一代將會復活（繁殖）。

顯然地，想使用程式建構這樣的遊戲並不難，單純就是迭代所有棋盤方格，計算每個細胞的鄰居數量，從而決定各方格細胞的下個狀態。

如果懶得寫程式，網路上也會有許多生命遊戲的模擬程式，例如Golly，有桌機或行動裝置的版本，下載回來後可用滑鼠點選各位置初始細胞狀態，模擬每一代的狀態變化。

在隨意玩耍生命遊戲的過程中，你也許會發現一些有趣的特性。

例如，有些初始狀態最後會形成穩定狀態，也就是最後始終是存活或死亡，而有些初始狀態最後在每一代或數代週期之間，重複相同的圖案（振盪狀態），運氣好的話，你可能還會發現一些會移動的圖案（會移動的振盪狀態）。

如果你玩不出這些狀態也沒關係，可以查看維基百科〈康威生命遊戲〉條目，試著在Golly中畫出對應的初始圖案，或者是載入Golly提供的既有初始狀態模式，看看各種有趣的生命遊戲演化。

基本細胞自動機 生命遊戲是二維的，狀態極為複雜，1983年英國電腦科學家StephenWolfram發表了基本細胞自動機（Elementarycellularautomaton），細胞只存在於一維的方格中，有左右兩個鄰居，各細胞的初始狀態為活著或死亡，若存活為1而死亡為0，細胞與其鄰居可能的狀態可以用三個位數的二進位數來表示，也就是000、001、010一直到111。

根據細胞與其鄰居可能的狀態，Wolfram制定細胞的演化規則是：在000時，細胞會維持死亡，也就是中間的位數依舊為0，而在001時，細胞復活，也就是中間的位數為1，以此類推。

而從000至111，細胞下一代的新狀態，各會是：0、1、1、1、1、0、0、0，我們通常將其稱為規則30。

如果將規則30每一代的狀態，依照舊代至新代，以由上至下的方式畫出來，會是個特殊圖案的三角形。

型態可參考維基百科〈Rule30〉條目中的照片，有趣的是，該條目中有張織錦芋螺的照片，螺殼上的圖案跟規則30非常相似。

因為細胞與其鄰居可能的狀態，使用000至111表示，下一代的狀態各可以對應至0或1，這表示演化規則會有256個可能性。

而在不同的規則下，Wolfram的基本細胞自動機如果畫出來，將會呈現不同的樣貌，例如，在規則90當中，初始狀態從000至111，對照的演化狀態是：0、1、0、1、1、0、1、0，所畫出來的圖案，竟然是碎形圖案謝爾賓斯基三角形（Sierpinskitriangle）（可參考先前專欄〈遞迴、碎形與數學〉）。

不過，並非每個規則都能生成類似自然界生成的圖案，因此，Wolfram在2002年發表的《ANewKindofScience》匯集了他的研究成果，其中將細胞自動機的演化，分為了四個類型：平衡（equilibrium）、暫時均勻（temporallyuniform）、混亂（chaotic）與複雜（complex）。

當中的平衡或暫時均勻，相當於之前提到的穩定或振盪；規則30屬於混亂，甚至可作為隨機產生器；規則110屬於複雜，像是類型二與三的混合，圖案可參考維基百科〈Rule110〉條目，而且被證明是圖靈完備（Turingcomplete）。

圖靈等價？ 如果你下載了之前提到的Golly，可能會注意到首頁中的文字跑馬燈，那是由生命遊戲產生的，我們可以在Golly的Life/Guns中找到golly-ticker。

這令人感到神奇，生命遊戲也可以執行運算？ Conway的生命遊戲或者是Wolfram的基本細胞自動機，具有狀態與規則，每一代的演化就是狀態轉移，很自然地，會令人聯想到有限狀態機，生命遊戲也能呈現一些重複模式，最有名的是Conway發現的滑行者（glider），以及在Conway的50英鎊懸賞下，由美國數學家BillGosper發表的槍（gun），可以不斷地發射出滑行者。

更多複雜行為的模式被發現，甚至可以自我複製。

在《深入理解運算原理》的〈康威的生命遊戲〉談到，Conway本人曾在1982年示範，如何用滑行者表示二進位資料流，以及設計AND、OR、NOT邏輯閘，從而完成邏輯運算，他只差一點就可以設計出可運作的機器。

而Wolfram在1985年亦曾經猜想，規則110或許能進行通用運算。

而Wolfram的助理MatthewCook也證明了規則110是圖靈完備，也就是它具有與圖靈機等價的運算能力。

實際上，Cook在Wolfram發表《ANewKindofScience》之前，就曾經在研討會上提出證明，然而，因為違反了保密協議，直到2004年，才發表了〈UniversalityinElementaryCellularAutomata〉。

在生命遊戲這方面，2002年PaulChapman實作了一個特殊的通用電腦，稱為LifeUniversalComputer，而PaulRendell在2010年基於生命遊戲，也設計了一個通用圖靈機。

複雜系統核心原則 我第一次接觸生命遊戲，是在冼鏡光著的《名題精選百則》中，當時只當它是個練習用的題目，而不以為意。

後來，在十幾年後的《深入理解運算原理》中，才再次看到生命遊戲的簡介。

但直到最近，於《Thenatureofcode》中看到基本細胞自動機，發現竟可構造謝爾賓斯基三角形而感到訝異，開始思考著這其中的道理究竟是什麼！ 或許也不需要訝異，正如《TheNatureofCode》中談到的複雜系統核心原則「複雜系統是由許多個體元件組成，個體並行地運作，相互之間存在簡單的關係，整體上表現出一些自發現象。

」遞迴是如此、碎形是如此，細胞自動機也是如此，順便一提，你知道巴斯卡三角形也隱含著謝爾賓斯基三角形嗎？（提示：將巴斯卡三角形中的奇數、偶數標示不同顏色！） 關於細胞自動機，還有許多有趣的事實，除了《深入理解運算原理》、《TheNatureofCode》，如果想要看到更多有趣的資料，我們可參考〈電腦裡的生命遊戲，等你挑戰讓生命無限延續！〉、〈一文讀懂細胞自動機的起源、原理和應用〉等文件。

專欄作者 林信良 因在網路上經營「良葛格學習筆記」（openhome.cc）而聞名，曾任昇陽教育訓練中心技術顧問、甲骨文教育訓練中心授權講師，目前為自由工作者，專長為技術寫作、翻譯與教育訓練。

喜好研究程式語言、框架、社群，從中學習設計、典範及文化。

閒暇之餘記錄所學，技術文件涵蓋C/C++、Java、Ruby/Rails、Python、JavaScript、Haskell等多個領域。

熱門新聞 可口可樂傳被勒索軟體攻擊，竊走161GB資料 2022-04-27 上市櫃公司年報揭露資安作為，已有台積電、京城銀十多家企業公布 2022-04-27 蘋果終止macOSServer 2022-04-25 居家隔離時間大縮短！指揮中心公布居家隔離3+4新規定，明日開始執行 2022-04-25 【企業為什麼要設立資安長】臺灣設立資安長動能來自法規遵循 2022-04-25 3+4居家隔離新政策今上路，指揮中心公布更多調整細節 2022-04-26 微軟揭露Linux的權限擴張漏洞 2022-04-27 【專家觀點：臺灣科技大學資管系教授查士朝】稱職資安長要懂得確認資安需求並做好資源分配 2022-04-25 Advertisement 專題報導 如何當一個稱職的資安長？ 友達數位製造轉型大解密 醫療HIS微服務化大改造 美國升起資安防護罩 儲存防寫應用重新崛起 更多專題報導