細胞自動機
細胞自動機（英語：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]
參照
[編輯]參考文獻
[編輯]- ^ 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 [2022-05-06]. doi:10.1016/S0022-0000(72)80013-8. （原始內容存檔於2022-05-06）.
- ^ 周成虎; 孫戰利 謝一春. 地理元胞自动机研究. 北京: 科學出版社. 2000: 26–51. ISBN 9787030081209.
- ^ 宣慧玉; 高寶俊. 管理与社会经济系统仿真. 武漢: 武漢大學出版社. 2000: 98-114. ISBN 9787307034075.
- ^ 陳國宏; 蔡彬清,李美娟. 元胞自动机：一种探索管理系统复杂性的有效工具. 中國工程科學. 2007, 9 (1): 28~32.
- ^ 5.0 5.1 5.2 Ilachinsky 2001，第12頁
- ^ Ilachinsky 2001，第13頁
- ^ Wolfram 2002，第231頁
- ^ Zenil, Hector. Compression-based investigation of the dynamical properties of cellular automata and other systems (PDF). Complex Systems. 2010, 19 (1) [2013-12-03]. （原始內容存檔 (PDF)於2017-08-09）.
- ^ G. Cattaneo, E. Formenti, L. Margara. Topological chaos and CA. M. Delorme, J. Mazoyer (編). Cellular automata: a parallel model. Springer. 1998: 239 [2013-12-03]. ISBN 978-0-7923-5493-2. （原始內容存檔於2021-04-14）.
- ^ Burton H. Voorhees. Computational analysis of one-dimensional cellular automata. World Scientific. 1996: 8 [2013-12-03]. ISBN 978-981-02-2221-5. （原始內容存檔於2021-04-14）.
- ^ Max Garzon. Models of massive parallelism: analysis of cellular automata and neural networks. Springer. 1995: 149. ISBN 978-3-540-56149-1.
- ^ Li, Wentian; Packard, Norman. The structure of the elementary cellular automata rule space (PDF). Complex Systems. 1990, 4: 281–297 [January 25, 2013]. （原始內容存檔 (PDF)於2016-06-25）.
外部連結
[編輯]- 複雜性科學 - 複雜適應性系統 - 細胞自動機 Cellular Automata （頁面存檔備份，存於互聯網檔案館）
- 第十二講 知識運作-細胞自動機(cellular automata; CA)（PPT網頁版）
