關於細胞自動機的研究,最早可追溯至1950年代,這篇文章想從生命遊戲(Game of life)開始談起,或許不少程式人也曾聽過或實作過這個簡單的遊戲。

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

Conway的生命遊戲

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

遊戲的規則是這樣的:如果細胞的鄰居為二個或三個,該細胞在下一代(generation)的狀態會是存活(穩定)。若細胞的鄰居小於一個或在四個以上,下一代將會死亡(孤單死或擁擠死)。死亡狀態的細胞若有三個存活狀態的鄰居,下一代將會復活(繁殖)。

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

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

在隨意玩耍生命遊戲的過程中,你也許會發現一些有趣的特性。例如,有些初始狀態最後會形成穩定狀態,也就是最後始終是存活或死亡,而有些初始狀態最後在每一代或數代週期之間,重複相同的圖案(振盪狀態),運氣好的話,你可能還會發現一些會移動的圖案(會移動的振盪狀態)。

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

基本細胞自動機

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

根據細胞與其鄰居可能的狀態,Wolfram制定細胞的演化規則是:在000時,細胞會維持死亡,也就是中間的位數依舊為0,而在001時,細胞復活,也就是中間的位數為1,以此類推。而從000至111,細胞下一代的新狀態,各會是:0、1、1、1、1、0、0、0,我們通常將其稱為規則30。

如果將規則30每一代的狀態,依照舊代至新代,以由上至下的方式畫出來,會是個特殊圖案的三角形。型態可參考維基百科〈Rule 30〉條目中的照片,有趣的是,該條目中有張織錦芋螺的照片,螺殼上的圖案跟規則30非常相似。

因為細胞與其鄰居可能的狀態,使用000至111表示,下一代的狀態各可以對應至0或1,這表示演化規則會有256個可能性。而在不同的規則下,Wolfram的基本細胞自動機如果畫出來,將會呈現不同的樣貌,例如,在規則90當中,初始狀態從000至111,對照的演化狀態是:0、1、0、1、1、0、1、0,所畫出來的圖案,竟然是碎形圖案謝爾賓斯基三角形(Sierpinski triangle)(可參考先前專欄〈遞迴、碎形與數學〉)。

不過,並非每個規則都能生成類似自然界生成的圖案,因此,Wolfram在2002年發表的《A New Kind of Science》匯集了他的研究成果,其中將細胞自動機的演化,分為了四個類型:平衡(equilibrium)、暫時均勻(temporally uniform)、混亂(chaotic)與複雜(complex)。

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

圖靈等價?

如果你下載了之前提到的Golly,可能會注意到首頁中的文字跑馬燈,那是由生命遊戲產生的,我們可以在Golly的Life/Guns中找到golly-ticker。這令人感到神奇,生命遊戲也可以執行運算?

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

更多複雜行為的模式被發現,甚至可以自我複製。在《深入理解運算原理》的〈康威的生命遊戲〉談到,Conway本人曾在1982年示範,如何用滑行者表示二進位資料流,以及設計AND、OR、NOT邏輯閘,從而完成邏輯運算,他只差一點就可以設計出可運作的機器。而Wolfram在1985年亦曾經猜想,規則110或許能進行通用運算。

而Wolfram的助理Matthew Cook也證明了規則110是圖靈完備,也就是它具有與圖靈機等價的運算能力。實際上,Cook在Wolfram發表《A New Kind of Science》之前,就曾經在研討會上提出證明,然而,因為違反了保密協議,直到2004年,才發表了〈Universality in Elementary Cellular Automata〉

在生命遊戲這方面,2002年Paul Chapman實作了一個特殊的通用電腦,稱為Life Universal Computer,而Paul Rendell在2010年基於生命遊戲,也設計了一個通用圖靈機

複雜系統核心原則

我第一次接觸生命遊戲,是在冼鏡光著的《名題精選百則》中,當時只當它是個練習用的題目,而不以為意。後來,在十幾年後的《深入理解運算原理》中,才再次看到生命遊戲的簡介。但直到最近,於《The nature of code》中看到基本細胞自動機,發現竟可構造謝爾賓斯基三角形而感到訝異,開始思考著這其中的道理究竟是什麼!

或許也不需要訝異,正如《The Nature of Code》中談到的複雜系統核心原則「複雜系統是由許多個體元件組成,個體並行地運作,相互之間存在簡單的關係,整體上表現出一些自發現象。」遞迴是如此、碎形是如此,細胞自動機也是如此,順便一提,你知道巴斯卡三角形也隱含著謝爾賓斯基三角形嗎?(提示:將巴斯卡三角形中的奇數、偶數標示不同顏色!)

關於細胞自動機,還有許多有趣的事實,除了《深入理解運算原理》、《The Nature of Code》,如果想要看到更多有趣的資料,我們可參考〈電腦裡的生命遊戲,等你挑戰讓生命無限延續!〉〈一文讀懂細胞自動機的起源、原理和應用〉等文件。

作者簡介


Advertisement

更多 iThome相關內容