元胞自動機

不同於一般的動力學模型，元胞自動機不是由嚴格定義的物理方程或函式確定，而是用一系列模型構造的規則構成。凡是滿足這些規則的模型都可以算作是元胞自動機模型。因此，元胞自動機是一類模型的總稱，或者說是一個方法框架。其特點是時間、空間、狀態都離散，每個變數只取有限多個狀態，且其狀態改變的規則在時間和空間上都是局部的。

具體解釋

元胞自動機的構建沒有固定的數學公式，構成方式繁雜，變種很多，行為複雜。故其分類難度也較大，自元胞自動機產生以來，對於元胞自動機分類的研究就是元胞自動機的一個重要的研究課題和核心理論，在基於不同的出發點，元胞自動機可有多種分類，其中，最具影響力的當屬S. Wolfram在80年代初做的基於動力學行為的元胞自動機分類，而基於維數的元胞自動機分類也是最簡單和最常用的劃分。除此之外，在1990年，Howard A.Gutowitz提出了基於元胞自動機行為的馬爾科夫機率量測的層次化、參量化的分類體系（Gutowitz,H. A.,1990）。下面就上述的前兩種分類作進一步的介紹。同時就幾種特殊類型的元胞自動機進行介紹和探討S. Wolfrarm在詳細分析研究了一維元胞自動機的演化行為，並在大量的計算機實驗的基礎上，將所有元胞自動機的動力學行為歸納為四大類（Wolfram. S.，1986):

⑴平穩型:自任何初始狀態開始，經過一定時間運行後，元胞空間趨於一個空間平穩的構形，這裡空間平穩即指每一個元胞處於固定狀態。不隨時間變化而變化。

⑵周期型：經過一定時間運行後，元胞空間趨於一系列簡單的固定結構（Stable Patterns）或周期結構（Perlodical Patterns)。由於這些結構可看作是一種濾波器（Filter），故可套用到圖像處理的研究中。

⑶混沌型：自任何初始狀態開始，經過一定時間運行後，元胞自動機表現出混沌的非周期行為，所生成的結構的統計特徵不再變止，通常表現為分形分維特徵。

⑷複雜型：出現複雜的局部結構，或者說是局部的混沌，其中有些會不斷地傳播。

分別描述

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

⑴均勻狀態，即點態吸引子，或稱不動點；

⑵簡單的周期結構，即周期性吸引子，或稱周期軌；

⑶混沌的非周期性模式，即混沌吸引子；

⑷這第四類行為可以與生命系統等複雜系統中的自組織現象相比擬，但在連續系統中沒有相對應的模式。但從研究元胞自動機的角度講，最具研究價值的具有第四類行為的元胞自動機，因為這類元胞自動機被認為具有"突現計算"(Emergent Computation）功能，研究表明，可以用作廣義計算機（Universal Computer）以仿真任意複雜的計算過程。另外，此類元胞自動機在發展過程中還表現出很強的不可逆（lrreversibility）特徵，而且，這種元胞自動機在若干有限循環後，有可能會 "死"掉，即所有元胞的狀態變為零。

元胞自動機

基本介紹