細胞自動機

維基百科,自由的百科全書
跳到: 導覽搜尋
生命遊戲:細胞自動機的例子。

細胞自動機英語:Cellular automaton),又稱格狀自動機元胞自動機,是一種離散模型,在可算性理論數學理論生物學都有相關研究。它是由無限個有規律、堅硬的方格組成,每格均處於一種有限狀態。整個格網可以是任何有限維的。同時也是離散的。每格於t時的態由t-1時的一集有限格(這集叫那格的鄰域)的態決定。每一格的「鄰居」都是已被固定的。(一格可以是自己的鄰居。)每次演進時,每格均遵從同一規矩一齊演進。

就形式而言,細胞自動機有三個特徵:

  • 平行計算(parallel computation):每一個細胞個體都同時同步的改變
  • 局部的(local):細胞的狀態變化只受周遭細胞的影響。
  • 一致性的(homogeneous):所有細胞均受同樣的規則所支配

構成[編輯]

一個標準的細胞自動機()由元胞、元胞狀態、鄰域和狀態更新規則構成。用數學表示為[1]

其中L為元胞空間;d為元胞自動機內元胞空間的維數;S是元胞有限的、離散的狀態集合;N為某個鄰域內所有元胞的集合;f為局部映射或局部規則。

元胞空間是元胞所分佈的空間網點的集合。理論上元胞空間在各個維向上是無限延伸的,為了能夠在計算機上實現,而定義了邊界條件,包括周期型、反射型和定值型[2]

一個元胞通常在一個時刻只有取自一個有限集合的一種狀態,例如{0,1}。元胞狀態可以代表個體的態度,特徵,行為等[3]。在空間上與元胞相鄰的細胞稱為鄰元,所有鄰元組成鄰域。

歷史[編輯]

細胞自動機最早由美籍數學家馮·諾依曼John von Neumann)在1950年代為模擬生物細胞的自我複製而提出的。但是並未受到學術界重視。直到1970年,任教於劍橋大學的英國數學家約翰·何頓·康威(John Horton Conway)設計了生命遊戲,經馬丁·葛登在《科學美國人》雜誌上介紹,才吸引了科學家們的注意。此後,英國學者史蒂芬·沃爾夫勒姆(Stephen Wolfram)對初等元胞機256種規則所產生的模型進行了深入研究,並用來描述其演化行為,將細胞自動機分為平穩型、周期型、混沌型和複雜型[4]

分類[編輯]

史蒂芬·沃爾夫勒姆在《一種新科學》和幾篇從80年代中期開始的論文中定義了四類,細胞自動機和其他幾個簡單的計算模型可分為根據他們的行為。元胞自動機的早期研究往往試圖確定具體規則的模式類型,他提出的分類是對規則本身分類的第一次嘗試。按照複雜性分類的秩序:

  • 1類:幾乎所有的初始模式迅速演變成一個穩定的,均勻的狀態。在初始模式的任何隨機性會消失。[5]
  • 2類:幾乎所有的初始模式迅速演化為穩定或振盪結構。一些在初始模式的隨機性可能會被過濾掉,但是還有一些保留。在初始模式的局部變化傾向於繼續保持局部性。[5]
  • 3類:幾乎所有的初始形態將會演變成一個偽隨機或混沌的形式。任何穩定的結構很快會被周圍的噪音破壞。在初始模式的局部變化有無限蔓延的傾向。[5]
  • 4類:幾乎所有的初始模式將會演變成相互作用的複雜和有趣的方式結構,並且局部結構的形成能夠長時間存在。[6]2類的穩定或振盪的結構可能是最終的結果,但需要達到這個狀態的步驟數目可能是非常大的,即使在初始模式比較簡單的情況下。初始模式的局部變化可能會無限蔓延。史蒂芬·沃爾夫勒姆已推測不是所有的4類細胞自動機能夠進行通用計算。這已被證明對於規則110和約翰·何頓·康威生命遊戲

根據史蒂芬·沃爾夫勒姆的說法,這些定義在本質上是定性的但是任有解釋一些空間。「……幾乎任何一般的分類方案都有不可避免的情況,比如說根據不同的定義會被分配到不同的類里。因此細胞自動機也是這樣:偶爾有規則……顯示不同類的一些特點。」[7]他的分類已經與一個類具有壓縮長度輸出的元胞自動機相匹配。[8]

已經有人在嘗試進行細胞自動機的正式嚴格分類根據史蒂芬·沃爾夫勒姆的分類。例如,Culik和Yu提出三種定義的類(並且第四個和它們不同),有時被稱為Culik-Yu 類;能夠被分到這種類里的問題被證明是不可判定的。[9][10][11]史蒂芬·沃爾夫勒姆的2類可劃分為穩定(定點)和振盪(周期)規則兩個小組。[12]

參照[編輯]

參考文獻[編輯]

  1. ^ S. Amoroso; Y.N. Patt. Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures. Journal of Computer and System Sciences. October 1972, 6 (5): 448–464 [2010年7月28日]. doi:10.1016/S0022-0000(72)80013-8. 
  2. ^ 周成虎; 孫戰利 謝一春. 地理元胞自動機研究. 北京: 科學出版社. 2000: 26–51. ISBN 9787030081209. 
  3. ^ 宣慧玉; 高寶俊. 管理與社會經濟系統仿真. 武漢: 武漢大學出版社. 2000: 98-114. ISBN 9787307034075. 
  4. ^ 陳國宏; 蔡彬清,李美娟. 元胞自動機:一種探索管理系統複雜性的有效工具. 中國工程科學. 2007, 9 (1): 28~32 [2010年7月28日]. 
  5. ^ 5.0 5.1 5.2 Ilachinsky 2001,第12頁
  6. ^ Ilachinsky 2001,第13頁
  7. ^ Wolfram 2002,第231頁
  8. ^ Zenil, Hector. Compression-based investigation of the dynamical properties of cellular automata and other systems (PDF). Complex Systems. 2010, 19 (1). 
  9. ^ G. Cattaneo, E. Formenti, L. Margara. Topological chaos and CA. (編) M. Delorme, J. Mazoyer. Cellular automata: a parallel model. Springer. 1998: 239. ISBN 978-0-7923-5493-2. 
  10. ^ Burton H. Voorhees. Computational analysis of one-dimensional cellular automata. World Scientific. 1996: 8. ISBN 978-981-02-2221-5. 
  11. ^ Max Garzon. Models of massive parallelism: analysis of cellular automata and neural networks. Springer. 1995: 149. ISBN 978-3-540-56149-1. 
  12. ^ Li, Wentian; Packard, Norman. The structure of the elementary cellular automata rule space (PDF). Complex Systems. 1990, 4: 281–297 [January 25, 2013]. 

外部連結[編輯]