元胞自動機的分類

元胞自動機的構(gòu)建沒有固定的數(shù)學(xué)公式，構(gòu)成方式繁雜，變種很多，行為復(fù)雜。故其分類難度也較大，自元胞自動機產(chǎn)生以來，對于元胞自動機分類的研究就是元胞自動機的一個重要的研究課題和核心理論，在基于不同的出發(fā)點，元胞自動機可有多種分類，其中，最具影響力的當(dāng)屬S. Wolfram在80年代初做的基于動力學(xué)行為的元胞自動機分類，而基于維數(shù)的元胞自動機分類也是最簡單和最常用的劃分。除此之外，在1990年，Howard A.Gutowitz提出了基于元胞自動機行為的馬爾科夫概率量測的層次化、參量化的分類體系(Gutowitz, H. A. ,1990)。下面就上述的前兩種分類作進(jìn)一步的介紹。同時就幾種特殊類型的元胞自動機進(jìn)行介紹和探討S. Wolfrarm在詳細(xì)分忻研究了一維元胞自動機的演化行為，并在大量的計算機實驗的基礎(chǔ)上，將所有元胞自動機的動力學(xué)行為歸納為四大類(Wolfram. S.，1986):
(1)平穩(wěn)型:自任何初始狀態(tài)開始,經(jīng)過一定時間運行后，元胞空間趨于一個空間平穩(wěn)的構(gòu)形，這里空間平穩(wěn)即指每一個元胞處于固定狀態(tài)。不隨時間變化而變化。
(2)周期型:經(jīng)過一定時間運行后，元胞空間趨于一系列簡單的固定結(jié)構(gòu)(Stable Paterns)或周期結(jié)構(gòu)(Perlodical Patterns)。由于這些結(jié)構(gòu)可看作是一種濾波器(Filter)，故可應(yīng)用到圖像處理的研究中。
(3)混沌型:自任何初始狀態(tài)開始，經(jīng)過一定時間運行后，元胞自動機表現(xiàn)出混沌的非周期行為，所生成的結(jié)構(gòu)的統(tǒng)汁特征不再變止，通常表現(xiàn)為分形分維特征。
(4)復(fù)雜型:出現(xiàn)復(fù)雜的局部結(jié)構(gòu)，或者說是局部的混沌，其中有些會不斷地傳播。從另一角度，元胞自動機可視為動力系統(tǒng)，因而可將初試點、軌道、不動點、周期軌和終極軌等一系列概念用到元胞自動機的研究中，上述分類，又可以分別描述為(譚躍進(jìn)，1996；謝惠民，1994；李才偉、1997)；
(1)均勻狀態(tài)，即點態(tài)吸引子，或稱不動點;
(2)簡單的周期結(jié)構(gòu)，即周期性吸引子，或稱周期軌;
(3)混沌的非周期性模式，即混沌吸引子;
(4)這第四類行為可以與生命系統(tǒng)等復(fù)雜系統(tǒng)中的自組織現(xiàn)象相比擬，但在連續(xù)系統(tǒng)中沒有相對應(yīng)的模式。但從研究元胞自動機的角度講，最具研究價值的具有第四類行為的元胞自動機，因為這類元胞自動機被認(rèn)為具有"突現(xiàn)計算"(Emergent Computation)功能，研究表明，可以用作廣義計算機(Universal Computer)以仿真任意復(fù)雜的計算過程。另外，此類元胞自動機在發(fā)展過程中還表現(xiàn)出很強的不可逆(lrreversibility)特征，而且，這種元胞自動機在若干有限循環(huán)后，有可能會 "死"掉，即所有元胞的狀態(tài)變?yōu)榱恪?
S·Wolfram還近似地給出了上述四種一維元胞自動機中各類吸引子或模式所占地比見 (表1-1)，可以看出，具有一定局部結(jié)構(gòu)的復(fù)雜模式出現(xiàn)的概率相對要小一些。而第三種混沌型則出現(xiàn)的概率最大，并且，其概率隨著k和r的增大而呈現(xiàn)增大的趨勢。

這種分類不是嚴(yán)格的數(shù)學(xué)分類，但S·Wolfram將眾多(也許所有)的元胞自動機的動力學(xué)行為歸納為數(shù)量如此之少的四類，是非常有意義的發(fā)現(xiàn)，對于元胞自動機的研究具有很大的指導(dǎo)意義。它反映出這種分類方法可能具有某種普適性，很可能有許多物理系統(tǒng)或生命系統(tǒng)可以按這樣的分類方法來研究，盡管在細(xì)節(jié)上可以不同，但每一類中的行為在定性上是相同的 (謝惠民，1994)。
理論上，元胞自動機可以是任意維數(shù)的。那么，按元胞空間的維數(shù)分類，元胞自動機
通�？梢苑譃�:
(l)一維元胞自動機:元胞按等間隔方式分布在一條向兩側(cè)無限延伸的直線上，每個元胞 (Cell)具有有限個狀態(tài)s，s∈S={s₁,s₂,...,s_k}，定義鄰居半徑r，元胞的左右兩側(cè)共有2r個元胞作為其鄰居集合N，定義在離散時間維上的轉(zhuǎn)換函數(shù)f:S^{2r 1}→S可以記為:
，S_i^t為第i個元胞在t時刻的狀態(tài)。
稱上述A={S,N,f}三元組(維數(shù)d≡1)為一維元胞自動機 (Amoroso，S，1972;李才偉，l997)。
對一維元胞自動機的系統(tǒng)研究最早，相對來講，其狀態(tài)、規(guī)則等較為簡單，往往其所有可能的規(guī)則可以一一列出，易于處理，研究也最為深入。目前，對于元胞自動機的理論研究多集中在一維元胞自動機上。S，Wolfram對元胞自動機的動力學(xué)分類也是基于對一維初等元胞自動機 (Elementary Cellular Automata)的分析研究得出的。它的最大的一個特征在于容易實現(xiàn)元胞自動機動態(tài)演化的可視化:二維顯示中，一維顯示其空間構(gòu)形，空間維;另外一維顯示其發(fā)展演化過程，時間維。
(2)二維元胞自動機:元胞分布在二維歐幾里德平面上規(guī)則劃分的網(wǎng)格點上，通常為方格劃分。以J. H. Conway的"生命游戲"為代表，應(yīng)用最為廣泛。由于，世界上很多現(xiàn)象是二維分布的，還有一些現(xiàn)象可以通過抽象或映射等方法，轉(zhuǎn)換到二維空間上，所以，二維元胞自動機的應(yīng)用最為廣泛，多數(shù)應(yīng)用模型都是二維元胞自動機模型。

(3)三維元胞自動機：目前，Bays(Bays,C,1988)等人在這方面做了若干試驗性工作，包括在三維空間上實現(xiàn)了生命游戲，延續(xù)和擴展了一維和二維元胞自動機的理論。
(4)高維元胞自動機：只是在理論上進(jìn)行少量的探討，實際的系統(tǒng)模型較少。Lee Meeker在他的碩士論文中，進(jìn)行了對四維元胞自動機的探索。