元胞自動機 Cellular Automata

出自集智百科
跳轉到: 導覽搜尋

元胞自動機(中文也譯作細胞自動機,英文名稱Cellular Automata或Cellular Automaton,縮寫成CA)是一種離散模型,廣泛應用於計算機科學、物理學、複雜系統,理論生物學和微觀結構模型等領域。元胞自動機同時也被稱為元胞空間,棋盤自動機(tessellation automata),同質結構,元胞結構,棋盤結構和迭代數組。[1]


元胞自動機由規則的元胞網格組成,每個單元格都處於有限狀態中的一種,例如打開狀態和關閉狀態(與耦合映象晶格 (coupled map lattice)相反)。網格可以是任意有限維數。對於每個單元格,都有一組定義為其鄰域的單元格。 每個單元格都將被定義一種狀態來作為初始狀態(時間t = 0)。根據一些固定的規則(通常是一種數學函數)[2] ,產生新的狀態(t增加1個單位)。單元格當前狀態及其附近單元格的狀態共同決定了該單元格的新狀態。一般而言,更新單元格狀態的規則對於每個單元格都是相同的,不隨時間變化,適用於整個網格。[3] 然而也有例外,例如隨機元胞自動機異步元胞自動機


20世紀40年代,這個概念最初是由當時在洛斯阿拉莫斯國家實驗室 (Los Alamos National Laboratory)工作的斯坦尼斯瓦夫•烏拉姆(Stanislaw Ulam)和約翰·馮·諾依曼 John von Neumann發現的。儘管20世紀50年代到60年代一直有學者在研究這個問題,但直到20世紀70年代,隨着康威生命遊戲(Conway's Game of Life)的問世(一個二維的元胞自動機),這個問題才引起學術界的關注。20世紀80年代,史蒂芬·沃爾夫勒姆 Stephen Wolfram對一維元胞自動機進行了系統的研究,他稱其為初等元胞自動機。他的研究助理馬修·庫克(Matthew Cook)指出,這些規則是圖靈完備(Turing-complete)的。Wolfram在2002年發表了《一種新科學 A New Kind of Science》這一著作,文中指出元胞自動機已在許多科學領域得到應用,包括計算機處理器和密碼學。


Wolfram基於動力學行為,將元胞自動機分為4類:

  • (1)平穩型:自任何初始狀態開始,經過一定時間運行後,元胞空間趨於一個空間平穩的構形,這裡空間平穩即指每一個元胞處於固定狀態。不隨時間變化而變化。
  • (2)周期型:經過一定時間運行後,元胞空間趨於一系列簡單的固定結構(Stable Paterns)或周期結構(Perlodical Patterns)。由於這些結構可看作是一種濾波器(Filter),故可應用到圖像處理的研究中。
  • (3)混沌型:自任何初始狀態開始,經過一定時間運行後,元胞自動機表現出混沌的非周期行為,所生成的結構的統計特徵不再變化,通常表現為分形分維特徵。
  • (4)複雜型:出現複雜的局部結構,或者說是局部的混沌,其中有些會不斷地傳播。從另一角度,元胞自動機可視為動力系統,因而可將初試點、軌道、不動點、周期軌和終極軌等一系列概念用到元胞自動機的研究中。

從另一角度,元胞自動機可視為動力系統,因而可將初始點、軌道、不動點、周期軌和終極軌等一系列概念用到元胞自動機的研究中,上述分類,又可以分別描述為:

  • (1)均勻狀態,即點態吸引子,或稱不動點;
  • (2)簡單的周期結構,即周期性吸引子,或稱周期軌;
  • (3)混沌的非周期性模式,即混沌吸引子;
  • (4)這第四類行為可以與生命系統等複雜系統中的自組織現象相比擬,但在連續系統中沒有相對應的模式。但從研究元胞自動機的角度講,最具研究價值的具有第四類行為的元胞自動機,因為這類元胞自動機被認為具有"突現計算"(Emergent Computation)功能,研究表明,可以用作廣義計算機(Universal Computer)以仿真任意複雜的計算過程。另外,此類元胞自動機在發展過程中還表現出很強的不可逆(lrreversibility)特徵,而且,這種元胞自動機在若干有限循環後,有可能會 "死"掉,即所有元胞的狀態變為零。

目錄

概述

紅色單元格是藍色單元格的摩爾鄰域
紅色單元格是藍色單元格的馮·諾依曼鄰域。擴展的鄰域也包括粉色單元格


模擬二維元胞自動機的一種方法是用一張無限大的方格紙,加上一套元胞規則來構成。每個正方形被稱為“單元格” ,每個單元格有兩種可能的狀態,黑色和白色。 單元格的鄰域是指周圍的單元格。 最常見的兩種鄰域類型有馮諾依曼鄰域(von Neumann neighborhood)和摩爾鄰域(Moore neighborhood)。前者由4個 正交相鄰的單元格組成。 後者包括馮諾依曼領域和斜對角相鄰的4個單元格。[4]對於每個單元格及其摩爾鄰域,有512(29)種可能的自動機模式。 對於每一種模式,規則表將確定在下一個時間段中中心單元格是黑色還是白色。康威生命遊戲就是這種模式的一個流行版本。 另一種常見的鄰域類型是擴展的馮諾依曼鄰域,它包括每個正交方向上最近的2個單元格,總共8個單元格。[4]這種規則的一般方程是 kks,其中 k 是一個單元格可能狀態的數目,s 是用來確定單元格下一個狀態的相鄰單元格的數目(包括要計算的單元格本身)。[5] 因此,在二維的摩爾鄰域中,可能出現的自動機模式共有229個,即1.34*10154個。



通常假設整個網格中除了有限數量的單元格處於不同狀態之外,其他的每個單元格具有相同的初始狀態。這些狀態值的分配被稱為配置(configuration)。[3]更籠統地說,人們有時假設整個網格從一開始時就具有周期性模式,只有有限數量的單元格違反了這個模式。這種假設在一維元胞自動機中很常見。


元胞自動機通常是在有限網格上模擬的,而不是在無限網格上。在二維空間中,整個網格將是一個矩形而不是一個無限平面。有限網格最大的問題就是如何處理邊緣的單元格。處理它們的方式將影響網格中所有單元格的值,一種方法是允許這些單元格中的值保持不變;另一種方法是為這些單元格定義不同的鄰域。

雖然可以認為邊緣單元格的鄰域較少,但是必須為其定義新規則。這些單元格通常以環形排列處理: 當一個單元格無上鄰域時,將該單元格相應位置的網格底部單元格作為上鄰域,當一個單元格無左鄰域時,將該單元格相應位置的網格右側單元格作為右鄰域。(這實質上模擬了無限周期的拼接,在偏微分方程領域有時被稱為周期邊界條件。)這可以想象為用膠帶把矩形的左右邊緣粘在一起形成一個管狀,然後把管的頂部和底部邊緣粘在一起形成一個圓環(甜甜圈形狀)。其他維度的網格也是這樣處理的。這種方法不僅解決了鄰域的邊界問題,而且易於通過使用模塊化計算功能編程。例如,在一維元胞自動機中,單元格 xit 的鄰居是{ xi-1t-1,xit-1,xi+1t-1} ,其中 t 是時間步長(縱軸),i 是一代中的索引(橫軸)。


圓環

研究歷史


20世紀40年代,烏拉姆在洛斯阿拉莫斯國家實驗室工作時,以簡單的晶格網絡為模型研究了晶體的生長。[6]與此同時,烏拉姆在洛斯阿拉莫斯的同事馮·諾依曼正在研究自複製系統的問題。他最初的設計是基於一個機器製造另一個機器的概念。這種設計被稱為運動學模型。[7][8]馮·諾依曼在開發這一設計時,逐漸意識到製造一個自我複製的機器人非常困難,並且需要花費巨大成本為機器人提供“一大堆零件”來製造複製品。馮·諾依曼在1948年的希克森研討會 Hixon Symposium上寫了一篇題為《The general and logical theory of automata》的論文。[3]烏拉姆建議使用離散系統來創建自我複製的還原論模型。[3][9]尼爾斯·阿爾·巴里切利對這些人工生命模型進行了許多早期的探索。


烏拉姆和馮·諾依曼在20世紀50年代後期創造了一種計算流體運動的方法。該方法的驅動概念是將流體視為一組離散單元格,根據其相鄰單元格的行為計算其運動。[9] 因此誕生了第一個元胞自動機系統。 與烏拉姆的晶格網絡一樣,馮·諾依曼的元胞自動機是二維的,其自複製器通過算法實現。這樣設計的結果是一個通用複製和構造器在具有很小鄰域的元胞自動機內工作(只有那些接觸的單元格是鄰域;對於馮·諾依曼的元胞自動機而言,只有正交的單元格是鄰域),其中,每個單元格有29個狀態。[10]馮·諾依曼通過設計一個20萬個元胞的結構,證明了在特定的模式下,單元格可以在給定的網格中無止境地自我複製。這種設計被稱為棋盤模型,也被稱為馮·諾依曼通用構造器。[11]


馮·諾依曼在實驗室的身份證照片


同樣在20世紀40年代,諾伯特·維納和阿圖羅·羅森布魯斯開發了一種具有元胞自動機特徵的可激發介質模型。[12]它用於心臟系統脈衝傳導的數學描述。 然而該模型並不屬於元胞自動機,因為信號傳播的介質是連續的,波前是曲線。[12][13]1978年,J.m. Greenberg和S. P. Hastings發展並研究出了一個真正的種可激發介質的元胞自動機,請參閱元胞自動機。維納和羅森布魯斯的原始著作中包含了許多見解,在現代關於心律失常和興奮系統的研究出版物中仍被經常引用。[14]


到20世紀50年代末,人們已經注意到,元胞自動機可以被視為並行計算機,特別是在20世紀60年代,一系列形式越來越詳細和技術性的定理(通常類似於圖靈機的定理)被證明具有形式化的計算能力。[10]


20世紀60年代,人們將元胞自動機作為動力系統的一種特殊類型進行了研究,首次建立了其與符號動力學中的數學領域的聯繫。1969年, Gustav Arnold Hedlund根據這一觀點[15]在論文中彙編了許多結果,至今該論文仍被認為是元胞自動機數學研究的開創性論文。最基本的結果是在Curtis-Hedlund-Lyndon 定理中將元胞自動機的全局規則集描述為移位空間]的連續自同態集。


1969年,德國計算機先驅康拉德·楚澤 Konrad Zuse出版了《Calculating Space》,提出宇宙的物理定律本質上是離散的,整個宇宙是在一個元胞自動機的確定性計算的輸出。 楚澤理論成為 數字物理學研究領域的基礎。[3]


也是在1969年,計算機科學家埃爾維·雷·史密斯Alvy Ray Smith完成了斯坦福大學關於元胞自動機理論的博士論文。許多論文都出自這篇論文: 他展示了各種形狀鄰域的等價性,如何把摩爾鄰域歸結為馮諾依曼鄰域,或者如何把任何鄰域歸結為馮諾依曼鄰域。[16] 他證明了二維元胞自動機具有計算通用性,通過引入一維元胞自動機,表明即使在簡單的鄰域內二維元胞自動機同樣具有計算通用性,也是如此。[17] 他展示了如何將複雜的馮諾依曼結構普遍性證明(以及由此產生的自複製機器)納入到一維元胞自動機計算普遍性的結果中。[18] 作為馮·諾依曼關於元胞自動機的書的德文版介紹,他撰寫了一份該領域的調查報告,其中引用了幾十篇參考文獻,這些文獻是多個國家的多個作者在過去十年左右時間的研究成果,常常被現代元胞自動機研究者所忽視。[19]



在20世紀70年代,一種名為生命遊戲的兩態、二維元胞自動機廣為人知,尤其是在早期的計算機界。該元胞自動機是約翰·何頓·康威 John Horton Conway發明的,馬丁·加德納 Martin Gardner在《Scientific American》的一篇文章中推廣[20] ,其規則如下:

  1. 任何單元格的鄰域單元格狀態為活的少於兩個,那麼該單元格的狀態就為死,這可能是由於人口不足造成的。
  2. 任何單元格具有兩個或三個狀態為活的鄰域單元格,那麼該單元格狀態為活。
  3. 任何單元格具有超過三個狀態為活的鄰域單元格,那麼該單元格狀態為死,這可能是由於人口過剩造成的
  4. 任何狀態為死的單元格的鄰域若正好有三個狀態為活的單元格,那麼在下一時間段中,該單元格狀態會變為活,就像繁殖一樣。


儘管簡單,該系統實現了令人印象深刻的多樣性行為,在表觀隨機性和順序之間波動。 生命遊戲最明顯的特徵之一就是“滑翔機”的頻繁出現,滑翔機的排列實質上是使自己在網格上移動。也可以安排自動機使滑翔機相互作用來執行計算。經過大量的努力,已經證明生命遊戲可以模仿通用圖靈機。[21] 在20世紀70年代初期,它主要被看做一個娛樂性主題,除了研究生命遊戲的特殊性和一些相關規則外,很少有人進行後續的研究工作。


史蒂芬·沃爾弗拉姆 Stephen Wolfram在考慮了自然界中如何形成違反熱力學第二定律的複雜模式後,於1981年中開始獨立從事元胞自動機的研究。[10]他的研究源於對神經網絡等建模系統的興趣。[10]1983年6月,他在《Reviews of Modern Physics》上發表了他的第一篇論文,研究了初等元胞自動機(特別是第30條規則)。[1][10]這些簡單規則行為的意想不到的複雜性使得沃爾弗拉姆懷疑自然界的複雜性可能是由於類似的機製造成的。[10]然而,他的研究使他認識到元胞自動機在模擬神經網絡方面的效果很差。此外,Wolfram還闡述了內在隨機性和計算不可約性的概念,[10]並提出第110條規則,這條規則可能是通用的——在20世紀90年代,Wolfram的研究助手馬修·庫克 Matthew Cook證明了這一事實。[22]


2002年,Wolfram發表了一篇1280頁的文章《a New Kind of Science》 其中詳細論述了關於元胞自動機的發現不是孤立的事實,而是可靠的,並且對所有科學學科都有重要意義。[10]儘管出版很混亂[23] [24]但該書並未對基於元胞自動機的物理學基本理論進行論證,儘管它描述了一些基於元胞自動機的具體物理模型,它也提供了基於性質不同而形成的抽象系統模型。[10]

分類

Wolfram在a New Kind of Science和20世紀80年代中期的幾篇論文中,將元胞自動機和其他幾種簡單的計算模型根據其行為進行分為四個類別。早期關於元胞自動機研究傾向於識別特定規則的模式類型,而沃爾弗拉姆的分類是首次嘗試對規則本身進行分類。按照複雜程度的順序,類別如下:
第1類: 幾乎所有初始模式都迅速演變為穩定的均勻狀態。初始模式中的任何隨機性都會消失。[9]
第2類: 幾乎所有初始模式都迅速演變為穩定或振蕩的結構。初始模式中的某些隨機性可能會被濾除,但仍然存在。初始模式的局部更改傾向於保持局部。[9]
第3類:幾乎所有初始模式都以偽隨機或混亂的方式演變。任何出現的穩定結構都會被周圍的噪音迅速破壞。初始模式的局部更改趨向於無限期擴散。[9]
第4類: 幾乎所有的初始模式都演變成以複雜而有趣的方式相互作用的結構,形成了可以長期存在的局部結構。[9]


第2類的穩定或振蕩結構可能是最終的結果,即使初始模式相對簡單,但達到這種狀態可能需要很多步。初始模式的局部變化可能會無限擴散。Wolfram 推測存在很多第四類元胞自動機,即使不是全部,規則110和康威的《生命遊戲》已經證明了這一點。


這些定義本質上是定性的,有一定解釋空間。根據 Wolfram 的說法:“...幾乎所有的通用分類方案都是一種定義對應一個類別。 元胞自動機的分類也是如此: 偶爾會有一些規則來展示出一個類的某些特徵和另一個類的某些特徵。”[10]Wolfram的分類是已根據經驗與元胞自動機輸出壓縮長度的聚類相匹配而得出的。[25]


受 Wolfram 分類法的啟發,人們已多次嘗試將元胞自動機以嚴格的形式分類。 例如,Culik 和 Yu 提出了三個具有明確定義的類(沒有一種對應自動機的第四類),這些類有時被稱為 Culik-Yu 類; 這些類之間的關係已被證明是難以確定的[26][27] [28] Wolfram 的第2類可以劃分為穩定(不動點)和振蕩(周期)規則的兩個子類。[29]


劃分4類動力系統的想法最初來自諾貝爾獎獲得者化學家伊利亞·普里高津 Ilya Prigogine,他確定了這4類熱力學系統: (1)熱力學平衡系統,(2)空間 / 時間均勻系統,(3)混沌系統,(4)具有耗散結構的複雜遠離平衡系統。[30]

可逆的

主條目:可逆元胞自動機
如果對於元胞自動機的每個當前結構,恰好有一個過去的結構(原像),則元胞自動機是可逆的。[31]如果我們把元胞自動機看作是從結構映射到結構的函數,那麼可逆性就意味着這個函數是雙射的。[31]如果元胞自動機是可逆的,那麼其時間逆轉行為也可以被描述為元胞自動機; 這個事實是Curtis-Hedlund-Lyndon定理的結果,該定理是元胞自動機的拓撲特徵。[32][33]對於不是每個結構都有預映像的元胞自動機,這些沒有預映像的結構稱為初始模式。[3]


對於一維元胞自動機,已知有一些可以確定規則是否可逆的算法。[34][35] 然而,對於二維及更高維元胞自動機,其可逆性是無法判定的;換言之,沒有一種以自動機規則作為輸入,並保證正確地判斷自動機是否可逆的算法。賈科·卡里 Jarkko Kari的證明與王浩平鋪的拼貼問題有關。[36]


由於可逆的元胞自動機遵循熱力學定律原理,因此可用於模擬諸如氣體和流體動力學等物理現象。這種元胞自動機具有專門構造的可逆規則。托瑪索·托佛利 Tommaso Toffoli諾曼·馬戈盧斯 Norman Margolus等人已經研究過這樣的系統。有幾種技術可以用來準確地構造具有已知的可逆元胞自動機。 常見的有二階元胞自動機分區元胞自動機,兩者都是以某種方式修改元胞自動機的定義。雖然這種自動機並不嚴格滿足上面給出的定義,但是它們可以由擁有足夠大的鄰域和狀態數的傳統元胞自動機來模擬,因此它們可以被認為是常規元胞自動機的子集。它們還證明了每一個可逆的元胞自動機都可以被一個分區元胞自動機模擬。[37][38]

完全的

一類特殊的元胞自動機是完全元胞自動機。完全元胞自動機中每個單元格的狀態由一個數字表示(通常是從有限集合中提取的整數值),t時刻的單元格取值僅取決於 t-1時刻鄰近單元格取值的和(可能包括該單元格)。[10][9]如果 t 時刻的單元格狀態取決於 t-1時刻的單元格狀態和其鄰近單元格狀態的總和,那麼稱其為外部完全元胞自動機。[9] 康威的生命遊戲就是一個外部完全元胞自動機的例子,其單元格取值為0和1; 外部完全元胞自動機的元胞自動機具有與生命相同的摩爾鄰域結構,有時被稱為仿生元胞自動機。[39]

相關的自動機

元胞自動機概念的概括有很多種。

基於六邊形單元而不是正方形的元胞自動機


一種方法是不使用矩形(立方體等)網格。例如,一個平面以規則六邊形作為單元格平鋪。在許多情況下,產生的細胞自動機相當於具有特殊設計的鄰域和規則的矩形網格。另一種方法是網格本身形狀不規則,如彭羅斯平鋪[40]


同樣,具有一定概率觸發規則的元胞自動機稱為隨機元胞自動機。對於不同模式下的時間t,概率規則將給出中心單元格在時間t+1時轉換為各種可能狀態的概率。有時規則很簡單,例如:“採取《生命遊戲》規則,但是在每個時間點上,每個單元格都有0.001%的概率會轉變為相反的顏色。”


鄰域或規則可能會隨時間或空間的變化而變化。 例如,初始單元格的新狀態可以由水平相鄰的單元格確定,但對於下一代,將使用垂直單元格來確定其狀態。


在元胞自動機中,一個單元格的新狀態不受其他單元格的新狀態影響。這也是可以改變的,例如,一個2×2的單元格塊可以由它自己和鄰近的單元格決定。


連續自動機像完全元胞自動機一樣,但是規則和狀態不是離散的(例如,使用狀態{0,1,2}的表),而是使用連續函數,並且狀態變為連續(通常為[0,1]中的值)。單個位置的狀態是有限個實數。某些元胞自動機可以通過這種方式產生液體擴散。


連續空間自動機具有連續的位置和時間。單個位置的狀態是有限個實數。狀態根據微分方程式改變。一個重要的例子是反應-擴散紋理,這是艾倫·圖靈 Alan Turing提出的用於解釋化學反應如何在斑馬和豹子身上形成條紋的微分方程。[41]當通過元胞自動機對其近似化時,它們通常會產生相似的模式。MacLennan[42]認為連續的空間自動機是一種計算模型。


有連續空間自動機的已知示例表現出類似於生命遊戲中的滑翔機的傳播現象。[43]


[圖形再生自動機是基於圖形再生系統的元胞自動機的擴展。[44]

初等元胞自動機

最簡單的元胞自動機是一維的,每個單元格具有兩種狀態,並且單元格的鄰域定義為在其任一側的相鄰單元格。一個單元格及其兩個相鄰單元格形成一個3個單元格的鄰域,因此鄰域有23 = 8個可能的模式。規則包括為每種模式確定單元格在下一代中是1還是0。然後有28 = 256個可能的規則。 [5]



這256個元胞自動機通常由其Wolfram代碼來引用,Wolfram代碼是Wolfram發明的標準命名規則,為每個規則賦予從0到255的數字。許多論文分析並比較了這256個元胞自動機。元胞自動機第30條第110條規則非常有趣。下面的圖像展示了由0包圍的1(在每個圖像的頂部)組成的初始結構的演變記錄。每一行單元格表示自動機歷史中的一代,其中t=0表示頂行。白色單元格表示0,黑色單元格表示1。


第30條元胞自動機規則

規則30
表格30.png


第30條元胞自動機規則表現出了第3類行為,這意味着即使是簡單的輸入模式(如所示)也會導致混亂的,看似隨機的演變。


第110條元胞自動機規則

規則110
表格110.png


像《生命遊戲》一樣,第110條元胞自動機規則表現出Wolfram所稱的第4類行為:它既不是完全隨機的,也不是完全周期重複的。局部結構以各種看起來複雜的方式出現並相互作用。 馬修·庫克Matthew Cook在1994年作為Wolfram的研究助手在《A New Kind of Science》的發展過程中證明了其中一些結構足夠豐富以支持普遍性。這個結果很有趣,因為第110條元胞自動機規則是一個非常簡單的一維繫統,難以進行工程設計以執行特定行為。因此,該結果為Wolfram的觀點提供了重要的支持,即4類系統天生就具有普遍性。1998年,庫克在聖塔菲研究所召開了有關元胞自動機的會議,但該證明被Wolfram阻止在會議上提出,因為Wolfram不想在《A New Kind of Science》出版之前公開證明。[45]因此,2004年,在庫克提出該證明十年後,終於在Wolfram的Complex Systems雜誌(第15卷,第1期)上發表。第110條元胞自動機規則是一些最小型通用圖靈機的基礎。[46]

規則空間

初等元胞自動機規則由8位字符串指定,所有初等元胞自動機規則都可以視為位於8維單元超立方體頂點上。這個單元超立方體是元胞自動機規則空間。對於下一個近鄰元胞自動機,規則由25 = 32位字符串指定,並且元胞自動機規則空間為32維單位超立方體。兩個規則之間的距離可以通過沿着超立方體的邊緣從一個頂點(代表第一條規則)和另一個頂點(代表另一條規則)移動所需的步數來定義。該距離也稱為漢明距離


元胞自動機規則空間讓我們產生了以下問題:具有相似動態行為的規則是否彼此“接近”。在二維平面上以圖形方式繪製高維超立方體仍然是一項艱巨的任務,超立方體中規則的粗定位器是基本規則的8位字符串中的bit-1(或次近鄰規則的32位字符串)。在規則空間的這些切片中,在不同的Wolfram類中繪製規則表明,第1類規則具有較少的bit-1,因此位於空間的一個區域中;而第3類規則具有比例更高的bit-1(50%)。[46]


對於較大的元胞自動機規則空間,表明第4類規則是第1類和第3類規則的過渡。[47]這一觀察結果是混亂邊緣這一短語的基礎,讓人聯想到熱力學中的相變

生物學

元胞自動機可以模擬某些生物學發生過程。
一些貝殼的圖案(如ConusCymbiola屬的貝殼)是通過自然元胞自動機生成的。這些色素細胞沿着貝殼的邊緣分布在一條狹窄的帶子上。每個細胞根據其鄰近的色素細胞的激活和抑制活性分泌色素,遵循一個自然的數學規則。[48] 當貝殼生長緩慢時,細胞帶會在貝殼上留下彩色圖案。例如,分布廣泛的Conus textile的圖案類似於 Wolfram第30條元胞自動機規則[48]
植物通過元胞自動機機制調節氣體的攝入和損失。葉子上的每個氣孔都充當元胞。[48]
可以用兩種狀態的二維元胞自動機模擬頭足類動物皮膚上的移動波型,每種狀態都對應於擴展或縮回的色素細胞。[70]
人們發明了閾值自動機來模擬神經元,並模擬諸如識別和學習之類的複雜行為。[9]
成纖維細胞與元胞自動機具有相似之處,因為每個成纖維細胞僅與其相鄰細胞相互作用。[49]

化學類型

Belousov-Zhabotinsky 反應是一個時空化學振蕩器,可以用元胞自動機模擬。20世紀50年代,阿納托爾·馬爾科維奇·扎博丁斯基 Anatol Markovich Zhabotinsky(擴展了鮑里斯·帕夫洛維奇·別洛烏索夫 Boris Pavlovich Belousov的工作)發現,當一層薄薄的均勻的丙二酸、酸化溴酸鹽和鈰鹽混合在一起並且不受干擾時,就形成了迷人的幾何圖案,例如同心圓和螺旋在介質中傳播。在1988年8月Scientific American雜誌的“Computer Recreations”部分中,[50]亞歷山大·基瓦丁·杜德尼 Alexander Keewatin Dewdney討論了由德國比勒菲爾德大學的 Martin Gerhardt 和 Heike Schuster 開發的元胞自動機。[51]該自動機產生的波型類似於Belousov-Zhabotinsky反應中的波型。

應用程序

電腦處理器


元胞自動機處理器是元胞自動機概念的物理實現,可以在計算機上處理信息。處理單元以相同單元的規則網格排列。網格通常是二維正方形或三維的正方體拼貼或平鋪。其他拼貼也是可能的,但尚未使用。單元狀態僅通過與相鄰單元的交互來確定,不存在直接與更遠的單元進行通信。[52] 其中一個這樣的元胞自動機處理器陣列配置就是脈衝陣列。元胞相互作用可以通過電荷,磁性,振動(聲子(在量子尺度上)),或其他任何物理方式。因此任何單元之間不需要電線。這與當今大多數計算機(von Neumann設計)中使用的處理器截然不同,後者被劃分為若干部分,這些部分可以通過線路與遠距離的部分進行通信。

密碼學


最初建議使用第30條元胞自動機規則作為可能密碼學的分組密碼。二維元胞自動機可用於構建偽隨機數生成器[53] 元胞自動機已被提出用於[1]單向函數是一個有限元胞自動機的演化,其逆向元素很難找到。根據規則,任何人都可以輕易計算未來狀態,但是很難計算歷史狀態。

糾錯編碼


D. Roy Chowdhury,S。Basu,I。Sen Gupta和P. Pal Chaudhuri在一篇論文中將元胞自動機應用於設計糾錯碼。這篇論文定義了一種使用元胞自動機構建單比特糾錯和雙比特錯誤檢測(SEC-DED)碼的新方案,並發布了一種用於該碼的快速硬件解碼器。[54]

建模物理現實

正如安德魯·伊拉欽斯基(Andrew Ilachinski)在“ 元胞自動機”中指出的那樣,許多學者提出了宇宙是否是元胞自動機的問題。[9]Ilachinski認為,這個問題的重要性可以通過一個簡單的觀察更好地理解。觀察描述如下:思考元胞自動機第110條規則的演變過程:如果它是某種“外來物理學”,那麼對觀察到的模式的合理描述是什麼?[9]如果觀察者不知道圖像是如何產生的,那麼這個觀察者最終可能會推測一些類似粒子的物體的運動。事實上,物理學家詹姆斯·克魯奇菲爾德 James P. Crutchfield為其構建了一套嚴格的數學理論,證明了元胞自動機中“粒子”在統計學上出現。[55]然後,隨着爭論的進行,有人可能會懷疑,目前在我們現有理解水平中,以粒子物理對象描述是合理的世界,在其基礎的階段是否可能是一個元胞自動機?這個基礎階段存在信息缺失問題,或者對於隨機順序出現的基礎數據的理解不完全問題。這些可能與元胞自動機矛盾。


雖然還未發展出符合此思路的完整理論,但有趣的是,這一假設的發展使學者們對如何在一個離散的框架內理解我們的世界產生了有趣且豐富的猜測。人工智能的先驅馬文·明斯基 Marvin Minsky研究了如何理解粒子與二維元胞自動機網格的相互作用。[56]最早的工作計算機Z3的發明者Konrad Zuse開發了一個不規則組織的網格,以解決粒子信息含量的問題。[57]最近,愛德華·弗雷德金Edward Fredkin揭示了他所說的“有限自然假說”,即“最終,物理學的每一個量,包括空間和時間,都將是離散的和有限的。”這一思想。[58]弗雷德金和沃爾夫勒姆是基於元胞自動機的物理學的有力支持者。2016年,傑拉德·霍夫特 Gerard't Hooft出版了一本書,詳細介紹了利用細胞自動機重建量子力學的想法。[59]


近年來,非標準計算方面的文獻也提出了其他建議。 Wolfram 的《A New Kind of Science》將元胞自動機視為理解包括物理在內的各種學科的關鍵。Ilabs創始人 Gabriele Rossi 與 Francesco Berto 和 Jacopo tagliabue 共同開發的參考模型數學,以一種新的“菱形十二面體”格子和獨特規則為基礎,展現了一個原始的二維/三維宇宙。這種模式滿足普遍性(相當於圖靈機)和完全可逆性(一個能滿足人們想輕鬆地保存各種數量而又不丟失任何信息的迫切要求),並且將其套用到一階理論中,從而對宇宙演化進行定量、定性描述。[60]

元胞自動機舉例

生命遊戲

生命遊戲是英國數學家約翰·康威(John Conway)在1970年發明的元胞自動機。它最初於1970年10月在《科學美國人》雜誌中馬丁·加德納(Martin Gardner,1914年11月21日-2010年5月22日)的“數學遊戲”專欄出現。

生命遊戲是一種二維的元胞自動機,每個元胞都有黑白兩種不同的狀態,每個元胞都有周圍八個方格作為鄰居。生命遊戲的規則如下:

  1. 如果一個元胞周圍有3個元胞為生,則該元胞為生(即該元胞若原先為死,則轉為生,若原先為生,則保持不變) 。
  2. 如果一個元胞周圍有2個元胞為生,則該元胞的生死狀態保持不變;
  3. 在其它情況下,該元胞為死(即該元胞若原先為生,則轉為死,若原先為死,則保持不變)

當所有的元胞都按照這個規則檢查它的鄰居,並運行起來後,我們可以得到非常複雜的動態過程。

Gospers glider gun1.gif

另外,生命遊戲中還會誕生出一種被稱為“滑翔機”的局部結構,它的動態運行情況如下圖所示:

創建縮圖錯誤: 無法將縮略圖保存到目標地點

“滑翔機”可以作為一種局部傳遞信息的結構。可以利用“滑翔機”搭建更加複雜的動態結構。

一維基礎元胞自動機

最簡單的元胞自動機就是一維的元胞自動機。在其上,每個元胞都有黑、白兩種顏色,每個元胞都有左右兩個鄰居。由於每個元胞有兩個狀態,這樣,當前元胞加上左右兩個鄰居一共就有8種狀態:

屏幕快照 2015-12-11 23.34.46.png

他們表示的狀態分別是:000,001,010,011,100,101,110,111,其中0表示白色,1表示黑色。

下面考慮規則,由於元胞自動機的規則就是根據每個元胞和它的鄰居的當前狀態轉移到下一個時刻該元胞的狀態。無論規則是什麼樣的黑箱,它的輸入就是上面列出的8種組合之一,因為表示的是每個元胞下一時刻的狀態,而狀態只可能有0、1兩種,則規則的輸出要麼是0,要麼是1。這樣,任何一個規則都是一個或者一組轉換,比如下圖表示的就是一條規則:

屏幕快照 2015-12-11 23.36.07.png

另外,若有一個規則是:“如果輸入的三個元胞中黑色方格只有1個,那麼下一時刻當前元胞就是黑色”可以表示成下面的圖:

屏幕快照 2015-12-11 23.36.54.png

下面我們再把目光轉到規則集上。由於每一條規則都是一個狀態或一組狀態的轉換,那麼把輸入的8種可能情況轉換到當前元胞的下一狀態。我們可以用一個轉換表表示一組規則集,例如:

屏幕快照 2015-12-11 23.37.37.png

這個規則集也可以用下面的一組數字表示為:

屏幕快照 2015-12-12 00.36.36.png

每一組規則集也可以表示成類似於上面的圖和表,例如下面的另外一組規則

屏幕快照 2015-12-12 00.36.43.png

由於鄰居加上當前元胞一共8種狀態,每一個狀態對應兩種可能轉換規則,所以規則一共就有2^8=256種,我們可以為每一個規則編碼,然後對其進行窮舉。

下面我們來考察這256中元胞自動機所具備的可能動態行為。對於一維的情況,我們假設所有的元胞都分布在一條直線上,並且直線的長度為300,也就是說有300個元胞在這條直線上,那麼一條斷續的橫線就是當前所有細胞狀態的一種分布。這些方格隨着時間變化,就形成了不同的橫線。我們把這些隨着時間變化的線縱向拼在一起形成了一個網格區域。其中縱軸表示時間的流逝(往下為正),橫軸為“元胞自動機在對應時刻的狀態,就能得到一幅圖像:

屏幕快照 2015-12-12 00.42.38.png

這個元胞的每一行都是某一個時刻元胞自動機的狀態。因而從上到下數第1、2、3、4、5、6行可以分別表示第1、2、3、4、5、6時間步的元胞自動機狀態。因此這裡的一個平面的圖案就是元胞自動機在時間上的發展動態。下面我們分別挑選幾種典型的動態情況示於下圖(下方的數字是元胞自動機的編碼):


屏幕快照 2015-12-12 00.42.44.png

屏幕快照 2015-12-12 00.44.21.png

110號元胞自動機屬於複雜類型,它的運行圖如下所示:

創建縮圖錯誤: 無法將縮略圖保存到目標地點

從圖中我們可以看出,110號元胞自動機存在着大量的局域化的結構,有些結構可以在元胞之間傳遞。它的動態行為既非秩序亦非隨機,屬於介於秩序與混沌邊緣的複雜類型。

NaSch模型

1992年,德國學者 Nagel 和 Schreckenberg 在第184號元胞自動機規則的基礎上提出了一維交通流CA模型,即,NS 模型(或NaSch模型)。[61]

1.png

184規則模擬交通流(1表示有車,0表示無車,並且每輛車只在其前面具有開放空間時(前面一個格子為 0)才向前移動。這裡前方定義為格子的右向)。

在其演化的每個步驟中,184規則自動機同時對所有細胞使用以下規則生成下一個陣列中的每個細胞,以確定每個細胞的新狀態: Swarma10-1547211614.jpeg

NaSch 模型是一個交通流模型,每輛車的狀態都由它的速度和位置所表示,其狀態按照以下演化規則並行更新。

NS模型的規則如下:

加速過程。如果車輛的速度低於最大速度,且前方有空餘的空間,那麼在下一個時刻,速度會增加1。

減速過程。如果車輛發現前方在某一確定距離內有其他車輛,並且這個距離要小於它的速度,那麼車輛的速度會減少。

隨機因素。設定了其他隨機因素,會導致車輛的速度減1,速度不低於零。

位置更新。車輛按照預定的方式前進。

Xi.jpg

縱軸是時間軸,橫軸是在某一時刻的路況情況。發現隨着時間的推移,原本沒有堵塞情況的路況會自動出現堵塞,並且擁堵情況會在道路上傳遞。

參考文獻

  1. 1.0 1.1 Wolfram, Stephen (1983). "Statistical Mechanics of Cellular Automata". Reviews of Modern Physics 55 (3): 601–644. http://www.stephenwolfram.com/publications/articles/ca/83-statistical/.
  2. Toffoli Tommaso; Margolus Norman (1987). "Cellular Automata Machines: A New Environment for Modeling". MIT Press: 27. https://books.google.com/books?id=HBlJzrBKUTEC&pg=PA27.
  3. 3.0 3.1 3.2 3.3 3.4 3.5 Schiff, Joel L (2011). "Cellular Automata: A Discrete View of the World". Wiley & Sons, Inc: 40. https://books.google.com/books?id=uXJC2C2sRbIC&pg=PA40.
  4. 4.0 4.1 Kier, Lemont B.; Seybold, Paul G.; Cheng, Chao-Kun (2005). Modeling Chemical Systems using Cellular Automata. Springer. ISBN 9781402036576.
  5. 5.0 5.1 Bialynicki-Birula, Iwo; Bialynicka-Birula, Iwona (2004). Modeling Reality: How Computers Mirror Life. Oxford University Press. ISBN 978-0198531005.
  6. Pickover, Clifford A. (2009). The Math Book: From Pythagoras to the 57th Dimension, 250 Milestones in the History of Mathematics. Sterling Publishing Company, Inc. p. 406. ISBN 978-1402757969.
  7. John von Neumann, "The general and logical theory of automata," in L.A. Jeffress, ed., Cerebral Mechanisms in Behavior – The Hixon Symposium, John Wiley & Sons, New York, 1951, pp. 1–31.
  8. Kemeny, John G. (1955). "Man viewed as a machine". Sci. Am. 192 (4): 58–67. Bibcode:1955SciAm.192d..58K. doi:10.1038/scientificamerican0455-58.; Sci. Am. 1955; 192:6 (errata)
  9. 9.00 9.01 9.02 9.03 9.04 9.05 9.06 9.07 9.08 9.09 9.10 Ilachinski, Andrew (2001). Cellular Automata: A Discrete Universe. World Scientific. ISBN 9789812381835.
  10. 10.00 10.01 10.02 10.03 10.04 10.05 10.06 10.07 10.08 10.09 10.10 Wolfram, Stephen (2002). A New Kind of Science. Wolfram Media. ISBN 978-1579550080.
  11. von Neumann, John; Burks, Arthur W. (1966). Theory of Self-Reproducing Automata. University of Illinois Press.
  12. 12.0 12.1 Wiener, N.; Rosenblueth, A. (1946). "The mathematical formulation of the problem of conduction of impulses in a network of connected excitable elements, specifically in cardiac muscle". Arch. Inst. Cardiol. México. 16: 205.
  13. Letichevskii, A. A.; Reshodko, L. V. (1974). "N. Wiener's theory of the activity of excitable media". Cybernetics. 8 (5): 856–864. doi:10.1007/bf01068458.
  14. Davidenko, J. M.; Pertsov, A. V.; Salomonsz, R.; Baxter, W.; Jalife, J. (1992). "Stationary and drifting spiral waves of excitation in isolated cardiac muscle". Nature. 355 (6358): 349–351. Bibcode:1992Natur.355..349D. doi:10.1038/355349a0. PMID 1731248.
  15. Hedlund, G. A. (1969). "Endomorphisms and automorphisms of the shift dynamical system". Math. Systems Theory. 3 (4): 320–3751. doi:10.1007/BF01691062.
  16. Smith, Alvy Ray. Cellular Automata Complexity Trade-Offs. http://alvyray.com/Papers/CA/TradeOff.pdf.
  17. Smith, Alvy Ray. Simple Computation-Universal Cellular Spaces. http://alvyray.com/Papers/CA/UniversalCA_1D.pdf.
  18. Smith, Alvy Ray. Simple Nontrivial Self-Reproducing Machines. http://alvyray.com/Papers/CA/alife2_optimized.pdf.
  19. Smith, Alvy Ray. Introduction to and Survey of Cellular Automata or Polyautomata Theory. http://alvyray.com/Papers/CA/PolyCA76.pdf.
  20. Gardner, Martin (1970). ""Mathematical Games: The fantastic combinations of John Conway's new solitaire game "life"". Scientific American 223 (223): 601–644. http://www.ibiblio.org/lifepatterns/october1970.html.
  21. Paul Chapman (2002). Life universal computer. http://www.igblan.free-online.co.uk/igblan/ca/.
  22. Mitchell, Melanie (4 October 2002). "Is the Universe a Universal Computer?". Science. 298 (5591): 65–68. doi:10.1126/science.1075073.
  23. Johnson, George (2002). The New York Times. https://www.nytimes.com/2002/06/09/books/review/09JOHNSOT.html.
  24. The Economist. 2002. http://www.economist.com/printedition/displayStory.cfm?Story_ID=1154164.
  25. Zenil, Hector (2010). "Compression-based investigation of the dynamical properties of cellular automata and other systems". Complex Systems 19 (1). http://www.complex-systems.com/pdf/19-1-1.pdf.
  26. G. Cattaneo; E. Formenti; L. Margara (1998). "Topological chaos and CA". In M. Delorme; J. Mazoyer (eds.). Cellular automata: a parallel model. Springer. p. 239. ISBN 978-0-7923-5493-2.
  27. Burton H. Voorhees (1996). Computational analysis of one-dimensional cellular automata.. World Scientific. pp. 8.
  28. Max Garzon (1995). Models of massive parallelism: analysis of cellular automata and neural networks. Springer. p. 149. ISBN 978-3-540-56149-1.
  29. Li, Wentian; Packard, Norman (1990). Complex Systems 4: 281–297. http://www.complex-systems.com/pdf/04-3-3.pdf.
  30. Nicolis (1974). "Dissipative Structures, Catastrophes, and Pattern Formation: A Bifurcation Analysis". PNAS 71 (7): 2748-2751. http://www.complex-systems.com/pdf/04-3-3.pdf.
  31. 31.0 31.1 Gutowitz, Howard, ed. (1991). Cellular Automata: Theory and Experiment. MIT Press. ISBN 9780262570862.
  32. Richardson, D. (1972). "Tessellations with local transformations". J. Computer System Sci. 6 (5): 373–388. doi:10.1016/S0022-0000(72)80009-6.
  33. Margenstern, Maurice (2007). Cellular Automata in Hyperbolic Spaces – Tome I, Volume 1. Archives contemporaines. p. 134. ISBN 978-2-84703-033-4.
  34. Amoroso, Serafino; Patt, Yale N. (1972). "Decision Procedures for Surjectivity and Injectivity of Parallel Maps for Tessellation Structures". J. Comput. Syst. Sci. 6 (5): 448–464. doi:10.1016/s0022-0000(72)80013-8.
  35. Sutner, Klaus (1991). [www.complex-systems.com/pdf/05-1-3.pdf "De Bruijn Graphs and Linear Cellular Automata"]. Complex Systems 5: 19-30. www.complex-systems.com/pdf/05-1-3.pdf.
  36. Kari, Jarkko (1990). "Reversibility of 2D cellular automata is undecidable". Physica D. 45 (1–3): 379–385. Bibcode:1990PhyD...45..379K. doi:10.1016/0167-2789(90)90195-U.
  37. Kari, Jarkko (1999). "On the circuit depth of structurally reversible cellular automata". Fundamenta Informaticae. 38: 93–107.
  38. Durand-Lose, Jérôme (2001). "Representing reversible cellular automata with reversible block cellular automata". Discrete Mathematics and Theoretical Computer Science. AA: 145–154. Archived from the original on 15 May 2011.
  39. The phrase "life-like cellular automaton" dates back at least to Barral, Chaté & Manneville (1992), who used it in a broader sense to refer to outer totalistic automata, not necessarily of two dimensions. The more specific meaning given here was used e.g. in several chapters of Adamatzky (2010). See: Barral, Bernard; Chaté, Hugues; Manneville, Paul (1992). "Collective behaviors in a family of high-dimensional cellular automata". Physics Letters A. 163 (4): 279–285. Bibcode:1992PhLA..163..279B. doi:10.1016/0375-9601(92)91013-H.
  40. Jacob Aron. "First gliders navigate ever-changing Penrose universe". New Scientist.. https://www.newscientist.com/article/dn22134-first-gliders-navigate-everchanging-penrose-universe.html.
  41. JMurray, J. "Mathematical Biology II". Springer.
  42. http://web.eecs.utk.edu/~bmaclenn/contin-comp.html
  43. Pivato, M: "RealLife: The continuum limit of Larger than Life cellular automata", Theoretical Computer Science, 372 (1), March 2007, pp. 46–68
  44. Tomita, Kohji; Haruhisa Kurokawa; Satoshi Murata (2009). "Graph-rewriting automata as a natural extension of cellular automata". Adaptive Networks Springer: 291-309. https://link.springer.com/chapter/10.1007/978-3-642-01284-6_14.
  45. Giles, Jim (2002). "What Kind of Science is This?". Nature. 417 (6886): 216–218. Bibcode:2002Natur.417..216G. doi:10.1038/417216a. PMID 12015565.
  46. Weinberg, Steven. "Is the Universe a Computer?". The New York Review of Books. http://www.nybooks.com/articles/archives/2002/oct/24/is-the-universe-a-computer/?pagination=false.
  47. Wentian Li; Norman Packard; Chris G Langton (1990). "Transition phenomena in cellular automata rule space". Physica D. 45 (1–3): 77–94. Bibcode:1990PhyD...45...77L. CiteSeerX 10.1.1.15.2786. doi:10.1016/0167-2789(90)90175-O.
  48. 48.0 48.1 48.2 Coombs, Stephen (2009). The Geometry and Pigmentation of Seashells. http://www.maths.nott.ac.uk/personal/sc/pdfs/Seashells09.pdf.
  49. Yves Bouligand (1986). Disordered Systems and Biological Organization. pp. 374–375.
  50. A. K. Dewdney, The hodgepodge machine makes waves, Scientific American, p. 104, August 1988.
  51. Gerhardt, M.; Schuster, H. (1989). "A cellular automaton describing the formation of spatially ordered structures in chemical systems". Physica D. 36 (3): 209–221. Bibcode:1989PhyD...36..209G. doi:10.1016/0167-2789(89)90081-x.
  52. Muhtaroglu, Ali (August 1996). "4.1 Cellular Automaton Processor (CAP)". Cellular Automaton Processor Based Systems for Genetic Sequence Comparison/Database Searching. Cornell University. pp. 62–74.
  53. Tomassini, M.; Sipper, M.; Perrenoud, M. (2000). "On the generation of high-quality random numbers by two-dimensional cellular automata". IEEE Transactions on Computers. 49 (10): 1146–1151. doi:10.1109/12.888056.
  54. Chowdhury, D. Roy; Basu, S.; Gupta, I. Sen; Chaudhuri, P. Pal (June 1994). "Design of CAECC - cellular automata based error correcting code". IEEE Transactions on Computers. 43 (6): 759–764. doi:10.1109/12.286310.
  55. J. P. Crutchfield, (1994). "The Calculi of Emergence: Computation, Dynamics, and Induction". Physica.D. http://csc.ucdavis.edu/~cmg/papers/CalcEmerg.pdf.
  56. Minsky, M. (1982). "Cellular Vacuum". International Journal of Theoretical Physics. 21 (537–551): 1982. Bibcode:1982IJTP...21..537M. doi:10.1007/bf02650183.
  57. K. Zuse, "The Computing Universe", Int. Jour. of Theo. Phy. 21, 589–600, 1982.
  58. E. Fredkin, "Digital mechanics: an informational process based on reversible universal cellular automata", Physica D 45, 254–270, 1990
  59. Gerard 't Hooft, 2016, The Cellular Automaton Interpretation of Quantum Mechanics, Springer International Publishing, DOI 10.1007/978-3-319-41285-6, Open access-[1]
  60. F. Berto, G. Rossi, J. Tagliabue, The Mathematics of the Models of Reference, College Publications, 2010
  61. Nagel, K., & Schreckenberg, M. (1992). A cellular automaton model for freeway traffic Kai Nagel, Michael Schreckenberg. Journal de physique I, 2(12), 2221-2229.


推薦文獻

  1. von Neumann, John; Burks, Arthur W. (1966). Theory of Self-Reproducing Automata. University of Illinois Press.
  2. Wolfram, Stephen (1983). "Statistical Mechanics of Cellular Automata". Reviews of Modern Physics. 55 (3): 601–644.
  3. Gardner, Martin (1970). "Mathematical Games: The fantastic combinations of John Conway's new solitaire game "life"". Scientific American (223): 120–123.
  4. Ilachinski, Andrew (2001). Cellular automata: a discrete universe. World Scientific. pp. 44–45.
  5. Wolfram, Stephen (2002). A New Kind of Science. Wolfram Media. ISBN 978-1579550080.
  6. Gutowitz, Howard, ed. (1991). Cellular Automata: Theory and Experiment. MIT Press.
  7. Ilachinski, Andrew (2001). Cellular Automata: A Discrete Universe. World Scientific.


相關詞條

在集智百科上,跟元胞自動機主題相關的詞條:

方格宇宙,這是張江老師分享的從另一個角度,解析元胞自動機,一探方格宇宙的奧秘。

自我複製的元胞自動機,該詞條介紹了一個可以自我複製的元胞自動機Java程序。

生命遊戲是最典型的元胞自動機,在這個詞條內有詳細的介紹,且有代碼演示。(待補充)

Python的元胞自動機模擬該詞條裡面有元胞自動機的python代碼演示,由計算士整理。

朗頓的螞蟻也是元胞自動機的一個例子,由克里斯托弗·朗頓 Christopher Langton,在該詞條內有詳細的介紹和對應的代碼演示。


編者推薦

針對元胞自動機的情況,整理一些國內的資源,推薦給大家:


本中文詞條由 用戶參與編譯, 審校,歡迎在討論頁面留言

本詞條內容源自wikipedia及公開資料,遵守 CC3.0協議。

個人工具
名字空間
動作
導覽
工具箱