第二十五章﹕生命遊戲-1

前面我們介紹了自組織現象和孤子現象。此類現象出現的原因，都與外力無關，而只與系統自身內部各單元之間的相互作用，特別是非線性作用有關。由於這種內部作用，通過自身演化，使得系統群體表現出某種自動結合在一起、形成有序結構的集體行為。

除了物理學之外，科學界的各個領域，以及社會、人文、經濟、網絡、市場等方方面面，都觀察到無序到有序的轉化過程。其中，生命進化是大家熟知的例子。生命起源一直是個重大的不解之謎，至今仍然眾說紛紜。生命之謎藏身於DNA分子的自我複製現象中，DNA的自我複製需要蛋白質的參與，而蛋白質產生又依賴於DNA攜帶的信息，這話聽起來有點像通常人們開玩笑時所調侃的“先有蛋還是先有雞”的悖論。事實上也是如此，這個雞與蛋的基本問題可以說至今未解，因為它在本質上問的就是生命如何起源？

無論如何，生命起源與自我複製的機制有關，科學家們很早就認識到這點。生物學家們在實驗室里研究分子如何自我複製的問題，而數學家及理論物理學家們則希望用某種數學模型，在計算機上來模擬產生自我複製的現象。早在上世紀50年代，大數學家馮·諾依曼為模擬生物細胞的自我複製而提出了‘自動細胞機’的概念。但當時並未受到學術界重視，直到1970年，隨着計算機技術的普及，劍橋大學的約翰·何頓·康維設計了一個叫做《生命遊戲》的電腦遊戲之後，‘自動細胞機’這個課題才吸引了科學家們的注意。

一九七零年十月, 美國趣味數學大師馬丁·加德納通過《科學美國人》雜誌的“數學遊戲”專欄, 將康維的“生命”遊戲介紹給學術界之外的廣大讀者，一時吸引了各行業一大批人的興趣。

所謂生命遊戲，事實上並不是通常意義上的”遊戲”, 它沒有遊戲玩家各方之間的競爭, 也談不上輸贏，可以把它歸類為“仿真遊戲”。事實上，也是因為它模擬和顯示的圖象，看起來頗似生命的出生和繁衍過程而得名為“生命”。

圖（25.1）：生命遊戲是二維的‘自動細胞機’

遊戲在一個類似於圍棋棋盤一樣的，但格子更為密集、數目更多、可以無限延伸的二維網中進行。例如，設想如圖（25.1a）的方格網。每個方格中都可放置一個生命細胞，每個生命細胞只有兩種狀態：“生”或“死”。在圖（25.1a）的方格網中，我們用黑色的方格表示該細胞為“生”, 空格（白色）表示該細胞為“死” 。或者換句話說，方格網中的黑色部分表示的是某個時候某種‘生命’的分布圖。生命遊戲想要模擬的就是：隨着時間的流逝，這個分布圖將如何一代一代的變化？

這裡又要用上我們在本系列文章中已經打過多次交道的‘迭代法’。在此我們不妨回憶一下曾經用過的迭代法：我們用迭代法畫出了曼德勃羅集、朱利亞集等各種分形；用迭代法研究過邏輯斯蒂系統中的倍周期分岔現象，系統的穩定性、從有序到無序的過渡；還用迭代法求解洛倫茨方程及限制性三體問題的數值解。那麼，這生命遊戲用的迭代法有點什麼不同呢？在畫分形圖和倍周期分岔圖時，我們考慮的是系統的‘長期行為’，畫出的是固定的，不隨時間而變化的圖形；畫微分方程的數值解時，曲線是隨時間而變化的函數，但是那只是空間中的一個點的軌跡。而在生命遊戲中，考慮的是整個平面上的‘生命細胞’分布情況的演化過程。也就是說，平面上每個點的‘生死’狀態都在不停地變化着。可想而知，這種迭代過程看起來將會生動有趣多了，否則，怎麼會把它稱之為‘遊戲’呢。

遊戲開始時, 每個細胞可以隨機地（或給定地）被設定為“生”或“死”之一的某個狀態, 然後，根據某種規則，計算出下一代每個細胞的狀態，畫出下一代的生死分布圖。

應該規定什麼樣的迭代規則呢？我們需要一個簡單的，但又反映生命之間（格子和格子之間）既協同、又競爭的生存定律。為簡單起見，最基本的考慮是假設每一個細胞都遵循完全一樣的生存定律；再進一步，我們把細胞之間的相互影響只限制在最靠近該細胞的8個鄰居中，參考圖（25.1b）。也就是說，每個細胞迭代後的狀態由該細胞及周圍八個細胞目前的狀態所決定。作了這些限制後，仍然還有很多方法，來規定‘生存定律’的具體細節。

例如，在‘康維的生命遊戲’中，規定了如下三條‘生存定律’，（被稱為規則B3/S23）：

1．   如果8個鄰居細胞中，有3個細胞為生，則迭代後該細胞狀態為生；

2.       如果8個鄰居細胞中，有2個細胞為生，則迭代後該細胞的生死狀態保持不變；

3.       在其它情況下，迭代後該細胞狀態為死。

上面的三條生存定律，你當然可以任意改動，發明出不同的‘生命遊戲’。但那幾條規則，也不是遊戲的發明者康維隨便想當然定出來的，其中暗藏着周圍環境對生存的影響在內。比如第一條，8個鄰居中有3個是活的，不多不少，這種情況也許對中間的小生命是最理想的，因此，迭代後結果總是為‘生’；第二條，8個鄰居中有2個是活的，人氣不太旺盛哦，不過也還算馬馬虎虎吧，對中間的小生命影響不大，所以康維認為，生死可以維持原狀；第三條就包括了好幾種情況啦，一是8個鄰居中活的數目多於4個，太擠啦，將造成物質缺乏，只有死路一條；或者是，8個鄰居幾乎全死光了，頂多只有一個奄奄一息的，那樣的話，中間的小生命也難以生存，死定了。

如此定下了生存定律之後，對格子網的某種初始分布圖，就可以決定每個格子下一代的狀態，然後，同時更新所有的狀態，得到第二代的分布圖。這樣一代一代地作下去，以至無窮。比如說，在圖（25.2）中，從第一代開始，畫出了四代細胞分布的變化情況。第一代時，圖中有四個活細胞（黑色格子），然後，讀者可以根據以上所述的四條生存定律，得到第二、三、四代的情況，觀察並驗證圖（25.2）的結論。

  圖（25.2）：二維生命細胞的四代演化過程

你可能會說，這樣的遊戲玩起來真是太不方便了！一格一格地算半天才走一步，也看不出趣味在何處。不過，有了計算機的幫助，就不難發現生命遊戲的趣味所在了。我們可以根據四條生存定律編好程序，輸入初始狀態圖，用計算機很快地來進行一代一代的運算和顯示。圖（25.3）所演示的便是計算機的仿真結果，初始分布如圖中n=0的小圖所示，接下來，便是第5、7、30、50、100、150代之後的分布圖。需要注意，圖中計算機畫出的圖形顏色正好與我們剛才的規定相反：黑色背景部分表示沒有‘生命’，其餘的彩色部分（除黑色之外的任何顏色）則表示生命的分布情形。

圖（25.3）：計算機模擬的生命遊戲迭代過程

（這個計算機生成的圖中，黑色部分表示‘死’，其它彩色表示‘生’）

點擊圖像連接到生命遊戲程序

http://www.tianfangyetan.net/cd/java/Life.html

如果仔細觀察圖（25.3）所示生命遊戲圖形的演化過程，能發現幾個有趣現象。看看最初始的分布圖（n=0）中，可將‘活’的細胞分為左中右三群：左邊一群不密不疏，最後的演化結果只剩下了一個固定的四邊圖形；中間的那一群非常分散，人煙過分稀少，第二代就全部死光了；最為有趣的是右邊那一群，開始時人口密集，擠得夠嗆！因此第二代也死掉不少。但是後來，人口逐漸遷移分散，群體得到了更大的空間，從n=50之後，這群人口大幅度增長，子孫繁衍到各處。

第二十六章﹕生命遊戲-2

林童在計算機上，玩自己剛寫出的‘康維的生命遊戲’程序。看着屏幕上五彩繽紛的圖像，跳躍不止的點點色彩，像夜空中閃爍不停的星星一樣，林童心中泛起一股成就感。特別當他設置出各種初始分布情形，玩了一陣之後，林童更加感到興趣盎然。

例如，如果你選擇“隨機設置”作為遊戲的初始分布，你會看到，遊戲開始運行後的迭代過程中，細胞生生死死，增增減減，變幻無窮。屏幕上“生命細胞”的圖案運動變化的情況，的確使人聯想到自然界中某種生態系統的變化規律：如果一個生命，其周圍的同類過於稀疏，生命太少的話，會由於相互隔絕，失去支持，得不到幫助而死亡；如果其周圍的同類太多而過於擁擠時，則也會因為缺少生存空間，且得不到足夠的資源而死亡。只有處於合適環境的細胞才會非常活躍，能夠延續後代，並進行傳播。林童也注意到，遊戲開始時的混亂無序的生命隨機分布，在按照康維的生存規律，迭代了幾百次之後，總是形成一些比較規則的圖案，像圖（26.1）所示的那樣。這看起來確實有點類似‘無序到有序’的轉化，或者是，李四說的‘自組織現象’。遊戲的演化方向和熱力學第二定律描述的那種‘趨於平衡’的演化方向大相庭徑，這個遊戲真能和‘生命起源’、或‘生命進化’，沾上點兒邊嗎？

圖（26.1）：生命遊戲模擬‘無序到有序’

生命遊戲激起了林童對生命科學的興趣，腦海里模糊地確定了一個自己將來發展的方向：用計算機技術來研究生命科學。不過當前，他饒有興味地看着圖（26.1）中n=511的那張圖，其中的圖案使他浮想聯翩。計算機屏幕上，隨着n的增大，圖案不斷變化：有的圖案最後定居在某個位置，似乎永遠不變了，除非遠方來的侵略者突然出現在旁邊，這種固定類型圖案使林童想起收斂於一點的經典吸引子；有的群體，則作很規則的振動，在幾個圖案之間不停地循環跳躍，就像邏輯斯蒂系統分岔成雙態平衡和多態平衡時的情形那樣；還有幾種圖案，頗似太空船、遊艇、或汽車，逍遙自在地週遊四方；有的群體，在不斷遊走的同時，自身圖案的形狀也變換無窮，這種情形是不是和邏輯斯蒂系統中出現混沌有點類似呢？從數學上，林童想不出這生命遊戲能和邏輯斯蒂混沌系統有什麼關係，書上也沒見有諸如此類的說法，只不過是似曾相識的現象此處彼處到處可見而已啊！儘管如此，林童仍然覺得這“生命遊戲”特別有意思，繼續觀察研究各種圖案。

圖（26.1）中n=511的圖，的確比n=0的初始圖，更有次序多了。其中看上去有序的每種圖案又互不相同、各有特色。在圖（26.2）中，我們畫出了幾種典型的分布情形，大概可以把這些圖案的演化方式分成下列幾種類型：靜止型、振動型、運動型、死亡型、不定型。

圖（26.2）：生命遊戲中幾種特別類型的分布圖案

例如，圖（26.2）中的“蜂窩”，“小區” 和“小船”，都屬於靜止型的圖案，如果沒有外界的干擾的話，此類圖案一旦出現後，便固定不再變化；而“閃光燈”，“癩蛤蟆”等，是由幾種圖形在原地反覆循環地出現而形成的振動型；圖中右上角的“滑翔機”和“太空船”，則可歸於運動類，它們會一邊變換圖形，一邊又移動向前。如果你自己用生命遊戲的程序隨意地試驗其它一些簡單圖案的話，你就會發現：某些圖案經過若干代的演化之後，會成為靜止、振動、運動中的一種，或者是它們的混合物。

此外，也還有可能得到我們尚未提及的另外兩種結果：一類是最終會走向死亡，完全消失的圖案；另一類是永遠不定變化的情形。就拿“最終死亡”的情況來說吧，“死”的速度可是有快有慢，有的曇花一現，不過幾代就斷子絕孫了（圖中的兩代死）；有的倒能繁榮昌盛幾百上千代：如上圖中間的第二個例子就能堅持130代。有趣的是，圖中的“老不死”是由兩個分圖案構成的，這兩個分圖案如果單獨存在，都會長生不死，糾集在一塊兒後，儘管也延續了130代，結果卻不一樣，最後以‘死’而告終。這可看着是一個“整體不等於部分之和”的實例。從變幻莫測的生命遊戲中，還有許許多多諸如此類的趣事，我們就不一一列舉了。

儘管生命遊戲中每一個小細胞所遵循的生存規律都是一樣的，但由它們所構成的不同形狀的圖案的演化行為卻各不相同。我們又一次地悟出這個道理：“複雜的事物（即使生命！），原來也可以來自於幾條簡單的規律！”。生命遊戲繼分形和混沌之後，又為我們提供了一個觀察從簡單到複雜的好方式。

生命遊戲的發明人約翰·康維，現為美國普林斯頓大學數學教授。康維除了致力於群論、數論、紐結理論及編碼理論這些多方純數學領域之外，也是遊戲的熱心研究者和發明者。在眾多貢獻之中，他的兩個最重要的成果都與遊戲有關：一是他在分析研究圍棋棋譜時發現了超實數（Surreal Number）；其二便是他在英國劍橋大學時發明的生命遊戲使他名聲大振，特別是經由《科學美國人》連續兩期的介紹推廣後，康維的名字在７０年代的大學及知識界幾乎人人皆知。上世紀的７０年代初，使用計算機還只是少數科研人員的專利，對生命遊戲中圖案演化行為的研究，有些熱心者甚至利用業餘時間在紙上進行！據馬丁·加德納後來回憶所述，當時整個國家科研基金的用途中，可能有價值上百萬美元的計算機時間，花費於並不十分合法的對“生命”遊戲的探索。業餘愛好者瘋魔於此遊戲的規則簡單卻變化無窮; 生物學家從中看到了”生態平衡”的仿真過程; 物理學家聯想到某種似曾相識的統計模型; 而計算機科學家們則競相研究“生命遊戲”程序的特點, 最後，終於證明了此遊戲與圖靈機等價的結論。對生命遊戲過分的熱心和瘋狂，大大超出了《科學美國人》的“數學遊戲”專欄的負荷能力，以至於當時還專門為此推出了一個名為《生命線》的通訊刊物。

另一件值得一提的趣事是：康維當時設置了一個五十美元的小獎金，給第一個能證明生命遊戲中某種圖形能無限制增長的人。這個問題很快就被麻省理工學院的計算機迷Bill Gosper解決了，這就是圖（26.2）中最下面一個圖案“滑翔機槍”的來源。圖（26.3）所示的是滑翔機槍在計算機上運行的情形：一個一個的“滑翔機”永不停止地、綿綿不斷地被“槍”發射出來。

圖（26.3）：生命遊戲中的滑翔機槍

這個實例證明了生命遊戲中存在無限增長的情形，看起來的確令人鼓舞：由幾條簡單的“生存定律”構成的“宇宙”中的“槍”，能不斷地產生出某種東西，就象機器製造出產品一樣。那麼，是否可能再進一步，找到某種圖案在演化過程中能自我複製，象生命形成的過程一樣呢？這不也正是馮·諾依曼當時提出‘自動細胞機’的原始想法嗎？

康維的生命遊戲的規則是可以改動的。於是，便產生了將生存定律稍加改動的‘生命遊戲系列’，1994年，一個叫Nathan Thompson的人發明了HighLife遊戲，將生存定律從康維的B3/S23改為B36/S23，並且從這個遊戲得到自我複製的圖案^【1】。再後來，也有人從原版的康維生命遊戲得到自我複製現象。

林童激動地告訴剛走進房間的王二和林零，用生命遊戲可以觀察到自我複製的圖案，解決生命起源之謎已經為時不遠啦，卻不料被王二嘲笑了一番：

“別太幼稚啦，那不過是個遊戲，離真正的、生物學意義上的生命還相距十萬八千里呢！計算機當然是個仿真大自然的好工具，但畢竟只是仿真，不是真的。不要像那個什麼史蒂芬·沃爾弗拉姆似的，以為計算就能解決一切問題了，真是大驚小怪、異想天開！”

林童被王二嘲笑得十分沮喪，也不知王二所說的沃爾弗拉姆，是何方神聖？不過讀者別為他着急，且讀下文，方知分曉。

參考資料：

【1】http://en.wikipedia.org/wiki/HighLife

【2】生命遊戲Java：http://www.bitstorm.org/gameoflife/

第二十七章﹕初級細胞自動機

西方有句諺語：“在木匠眼裡，月亮也是木頭做的。”

古希臘哲學家泰勒斯說：萬物之本是水。他的學生畢達哥拉斯說：萬物之本是數。再後來又有赫拉克利特說：萬物之本是火。中國哲學家孟子以心為萬物之本。近代的哲學家有了物理知識，則說：萬物之本是原子、電子等基本粒子。看來，哲學家們和木匠異曲同工，都希望把複雜的世界追根朔源到某一種簡單的、自己理解了的東西。

如今這個計算機時代，有人宣稱說：萬物之本是計算。

這個人就是上世紀80年代後期開發著名的《數學》Mathematica符號運算軟件的美國計算機科學家，史蒂芬·沃爾弗拉姆(Stephen Wolfram)。

實際上，沃爾弗拉姆並不是提出“萬物之本是計算”的第一人。MIT計算機實驗室前主任弗雷德金，早在上世紀80年代初就提出：“終極的實在不是粒子或力，而是根據計算規則變化的數據比特。”著名物理學家費曼在1981的一篇論文裡也表達過類似的觀點。

不過，沃爾夫勒姆沿着這條路走得更遠。從古至今困擾人們的三個基本哲學問題：生命是什麼？意識是什麼？宇宙如何運轉？按照沃爾夫勒姆在他的磚頭級巨著“新科學”里的“計算等價原理”，生命、意識都從計算產生，宇宙就是一台‘細胞自動機’。

被人們稱為天才的沃爾弗拉姆一九五九年生於倫敦，十五歲發表他的第一篇科學論文，二十歲獲得美國加州理工學院的物理博士學位。之後，又榮獲麥克阿瑟基金會的“天才”獎。當時，他將此獎項所獲得的十二萬五千美元的獎金全部用於了他感興趣的基本粒子物理及宇宙學等方面的研究。

八十年代初期，即將離開加州理工學院，前往普林斯頓高等研究院進行研究的沃爾弗拉姆在一次研討會上，初識了“細胞自動機”的理論，頗有一見鍾情、相見恨晚的樣子，一頭扎進細胞自動機的研究之中。

沃爾弗拉姆在八十年代後期，因為開發了著名的《數學》符號運算軟件而聲名大振，且獲得了商業上的成功。進入九十年代後，他便躲進小樓成一統，繼續他所痴迷的細胞自動機工作，潛心著作一部“曠世之作”。直到2002年，沃爾弗拉姆奮戰10年，經過無數次的敲鍵盤、移鼠標，終於產生出作者狂妄地自我宣稱是“與牛頓發現的萬有引力相媲美的科學金字塔”的巨著，名為：《一種新科學》。

在這部1200頁的重量級著作中，沃爾弗拉姆將他所偏愛的一維自動細胞機中的“規則 110”的精神光大發揚，貫穿始終。根據書中的觀點，各種各樣的複雜自然現象，從彈子球、紙牌遊戲到湍流現象；從樹葉、貝殼、等生物圖案的形成，到股票的漲落，實際上都受某種運算法則的支配，都可等價於“規則 110” 的細胞自動機。沃爾弗拉姆認為“如果讓計算機反覆地計算極其簡單的運算法則，那麼就可以使之發展成為異常複雜的模型，並可以解釋自然界中的所有現象”，沃爾弗拉姆甚至更進一步地認為宇宙就是一個龐大的細胞自動機，而“支配宇宙的原理無非就是區區幾行程序代碼”。

《一種新科學》的出版在當時引起轟動，初版五萬冊在一星期之內銷售一空，但是，學術界大多數專家們對此書的評價卻不高。對沃爾弗拉姆傲慢自大、忽視前人的工作、自比牛頓的做法，更是嗤之以鼻，認為這是使用商業手段，對不熟悉細胞自動機的廣大讀者的一種誤導。事實上，沃爾弗拉姆並未創立什麼“新科學”，由馮·諾依曼提出的細胞自動機的理論，已有五十多年的歷史，這個理論，以及基於複雜源於簡單的道理的‘複雜性科學’，一直都是科學界的研究課題。

沃爾弗拉姆雖然言過其實，但他對細胞自動機的鐘愛，對科學的執着，仍然令人佩服。況且，沃爾弗拉姆也不僅僅是空口說白話，而是用計算機進行了大量的論證和研究。比如，他認定了宇宙是個龐大的細胞自動機，但是有很多種不同的細胞自動機啊，宇宙到底是根據哪種細胞自動機運轉的呢？我們在上一章中介紹過的康維的生命遊戲，只是眾多二維細胞自動機中的一種，如果變換生存定律，可以創造出一大堆不同的生命遊戲來。此外，除了二維的細胞自動機，還可以有一維、三維、甚至更多維的細胞自動機。那麼，宇宙遵循的是哪一種呢？

沃爾弗拉姆想，首先應該從最簡單的一維細胞自動機開始研究。

像生命遊戲那種二維細胞自動機，是將平面分成一個一個的格子。因此，一維細胞自動機就應該是將一維直線分成一截一截的線段。不過，為了表示得更為直觀一些，我們用一條無限長的格點帶來表示某個時刻的一維細胞空間，如圖（27.1a）所示。用格子的白色或黑色來表示每個細胞的生死兩種狀態。並且，只考慮最相鄰的兩個細胞，也就是與其相接的“左”、“右”兩個鄰居的影響。如此所構成的最簡單的細胞自動機被稱為初級細胞自動機。

圖（27.1）：初級細胞自動機有256種

到底有多少種初級細胞自動機呢？一個細胞加上它的左右兩個鄰居，這三個細胞的生死狀態（輸入），決定了該細胞下一代（輸出）的狀態。因為三個細胞的狀態共有八種不同的組合，因此，如圖（27.1b）所描述的，初級細胞自動機的輸入有八種可能性。對每一種可能的輸入，下一代的中間那個細胞都有‘生’或‘死’兩種狀態可選擇。所以，總共可以組合成2⁸=256種不同的生存定律。也就是說，有256種不同的初級細胞自動機。

和我們介紹生命遊戲一樣，圖（27.1b）中用二進制的0（空格）代表‘死’，1（黑色格子）代表‘生’。首先，將輸入可能的八種情況按照111、110、101、100、011、010、001、000的順序從左至右排列起來，然後，八種輸入所規定的輸出狀態形成一個八位的二進制數。將此二進制數轉換成十進制，這個小於256的正整數便可用作初級細胞自動機的編碼。例如，圖（27.1c）所示的輸出狀態可以用二進制數00011110表示，將其轉換成十進制數之後，得到2⁴+2³+2²+2¹ = 30。我們便把這個生存定律代表的初級細胞自動機，稱為‘規則30’。

圖（27.2）：初級細胞自動機‘規則30’的時間演化圖

初始時刻只有中間一個細胞為‘生’

Java program

http://mokslasplius.lt/rizikos-fizika/en/wolframs-elementary-automatons

為了顯示一維細胞自動機中，細胞狀態不同瞬時的演化情況，我們將每一個相繼時刻對應的的格點帶附在上一時刻對應的的格點帶下面。如圖（27.2）所示，在t0時刻的格點帶，是一條只有中間一個格點為‘黑’，其餘格點均為‘白’的左右延伸的長帶子。圖中，垂直向下的方向表示時間的流逝。因為加了一個時間軸，所以，雖然是一維細胞自動機，而計算機屏幕顯示出來的卻是一個二維格點圖。圖（27.2）顯示了規則30的演化，圖（27.3）給出了更多其它規則的初級細胞自動機的演化圖形。

圖（27.3）：初級細胞自動機的時間演化圖

圖像來自Wolfram：

http://mathworld.wolfram.com/ElementaryCellularAutomaton.html

在沃爾弗拉姆發表的一系列論文中，對一維細胞自動機的代數、幾何、統計性質作了系統深入的研究和分類。他還特別對其中初級細胞自動機的“規則 30”和“規則 110”的有趣性質情有獨鍾。圖（27.4）給出這兩種規則對於隨機初始值的時間演化圖。“規則 30”之所以特別是因為它的“混沌”行為，例如我們可以考查中心細胞的狀態隨時間演化所得到的二進制序列：1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, ...，可以證明，這是一個無窮不循環的偽隨機序列。“規則 110”則更為有趣：在隨機的初始條件下，卻產生出好些看起來在一定程度上“有序”、但是又永不重複的圖案。“規則 110”似乎揭示了無序中的有序，混沌之中包含着的豐富的內部結構，隱藏着更深層次的規律。沃爾弗拉姆的一個年輕助手庫克後來（1994年）證明，“規則 110”是等效於通用圖靈機的。

圖（27.4）：規則30和規則110

如何理解一個初級細胞自動機“等效於通用圖靈機”呢？從生物學的角度看，細胞自動機的每一次迭代變化表現為細胞的生生死死，而從計算機科學的角度，每次演化卻可看作是完成了一次‘計算’。

查查計算機的歷史，曾經使用過一條長長的穿孔紙帶作為輸入輸出，這聽起來和我們這兒每個離散時刻的格子帶有些類似。格點帶上細胞的黑白生死分布，就對應於計算機紙帶上的（0/1）“符號串”。可以想象，如果我們有適當的編碼方法，就能將任何數學問題，包括它的初值和算法，變成一列符號串，寫到初始的第一條格子帶上。然後，根據細胞自動機內定的變換規則，可以得到下一時刻的符號串，也就是說，完成了一次“計算”。依此類推，時間不斷地前進，“計算”便一步一步地進行，直到所需要的結果。這個過程，的確與計算機的計算過程類似。

但是，並非所有規則的細胞自動機，都能等同於真正的計算機，還得看看它的智商如何？上面說過，我們有256種不同規則的細胞自動機，它們的智商高低不同，各具有不同的“計算”能力，。

例如，讓我們考查一下圖（27.3）所顯示的256個初級細胞自動機中的幾個特例：

1.  首先，象“規則 255”這樣的，完全談不上什麼計算能力，連“識別”能力都沒有，因為無論對什麼“數”，經它“計算”一次之後，全部一抹‘黑’，這點從它的規則定義也可看出來；“規則0”也一樣，全部一抹‘白’。

2.  接着，我們再來看象“規則 90”那一類的，時間演化圖有點象帕斯卡三角形的那種。這種情況的結果太規矩了，一個呆腦瓜，肯定計算能力有限，第一條的數據再複雜，猶如“對牛彈琴”一樣。

3.  另外，象“規則 30”那樣的，似乎較好一些，但邏輯雜亂無章，是個胡作非為、不聽指揮的傢伙。

4.  最後，唯有像“規則 110”這樣的，計算能力才達到標準，被證明與通用圖靈機是計算等效的。

…………

林童看完了有關‘初級細胞自動機’的介紹，閉着眼睛遐思冥想。王二沒錯！月亮的確不是木頭做的，我們的世界也不能單靠計算而算出來。但是，分形、混沌、以及非線性科學中的這些數學模型，以及計算機迭代的方法，對理解大自然還是很有用處的。林童想，科學真是太有趣、太迷人了！科學就像一座美麗宏大的花園，從分形和混沌這幾支科苑奇葩，他似乎看到了滿園的綠草如茵、花果飄香。林童想着想着，不知不覺地進入了夢鄉，夢中，他倘佯在百花叢中……

×××××××××××××××××××××××××××××××××××××××××××××＊＊＊＊＊＊＊＊

××　 　如果想繼續看我的系列科普的萬維網友，請到如下地址：  　　　　　　**

***　　科學網博客：http://blog.sciencenet.cn/u/tianrong1945 

＊＊  　系列科普目錄：http://blog.sciencenet.cn/blog-677221-601960.html