細胞自動機

為了理解細胞自動機，可看一個簡單例子：找一張畫有許多格子的圖紙，用鉛筆塗黑其中一些格子就可得到一個圖案（樣式）。第一排也許有一個或幾個格子被塗黑了，而一個簡單的細胞自動機是確定某種簡單的規則，從第二排開始往下畫出新圖案來。具體到每一行中的每一個格子，要觀察其上一行的對應格子及該對應格子兩邊的情況，然後根據這三個格子是否被塗黑，以及黑白格子如何相鄰的已定規則（比如，當這三個格子從左至右分別為黑、黑、白時，其正下面的格子為白，否則為黑），確定當前的格子是塗黑還是留白。如此反覆進行下去。一條或一組這樣的簡單規則及簡單的初始條件就構成了一個細胞自動機。

細胞自動機論主要研究由小的計算機或部件，按鄰域連接方式連接成較大的、并行工作的計算機或部件的理論模型。

諾伊曼細胞空間的所有細胞都在整數網格的結點上，細胞個數為無限。它滿足下列條件：各個細胞都是確定的摩爾型有限自動機；採取五鄰域一致連接模式（所有細胞有同樣形狀的鄰域）；不帶外部輸入，不向外部輸出；並且是靜態的（鄰域不隨時間改變）。一般的細胞空間不必要這些條件限制，故此外還有非確定型細胞空間、米雷型細胞空間、連接模式非一致的細胞空間、帶外部輸入的細胞空間以及動態的細胞空間等。

棋盤格空間是細胞空間的一個直接推廣。它有分配到各個細胞的統一的外部輸入。或者說，棋盤格空間是一個程序控制的細胞空間。棋盤格空間里的每一個細胞能夠被想象為有一個局部轉移函數的有限集合。因此，棋盤格空間有一個全局轉移函數的有限集合。程序中的各個“指令”選擇在該時刻的轉移中所使用的全局轉移函數。

絕大多數細胞自動機產生的都不過是乏味的單調圖案，但有一些卻大出人們的意料之外。

（1）最簡一維細胞自動機

最簡單的一維細胞自動機的狀態集合為兩個元素{0,1}。鄰居是一個半徑為1的區域，也就是每一個方格的左、右兩個方格是它的鄰居，這樣每一個方格單元和它的鄰居可以表示如下：

黑色的方格是當前細胞，兩邊的灰色方格是它的鄰居。由於狀態集只有{0，1}兩個狀態，也就是說方格只能有黑、白兩種顏色，那麼任意的一個方格加上它的兩個鄰居，這3個方格的狀態組合一共就有8種。

他們表示的狀態分別是：111，110，101，100，011，010，001，000。也就是說對於狀態數為2，鄰居半徑為1的所有一維細胞自動機的鄰居和其自身的狀態組合就這8種。

（2）規則與編號

下面考慮規則。假設當前考慮的細胞為ci，他在t時刻的狀態為si,t，而它的兩個鄰居狀態為si-1,t，si+1,t，則ci在下一時刻的狀態為si,t+1，則轉換規則用函數表示為：

si,t+1=f(si-1,t,si,t,si+1,t)

其中，si,t∈{0,1}，對於任意的i和t

由於在我們這個最簡單的細胞自動機中每個細胞和它的鄰居狀態的所有可能組合就上面列出來的8種，所以它的輸入就是上面列出的8種組合之一，輸出表示的是每個細胞下一時刻的狀態，而狀態只可能有0、1兩種，則規則的輸出要麼是0，要麼是1。這樣，任何一個規則就是一個或者一組轉換，

那麼這組規則就對應著編碼：10100011，也就是把八個位置上的方格進行一個排列。我們可以把輸出部分的二進位編碼轉換成十進位數的形式：163，這就是該細胞自動機的編碼。當狀態數增多，半徑增大的時候，這種編碼方式就不實用了，我們需要用另一種方式來編碼。考慮下面這樣的規則若有一個規則是：“如果輸入的三個方格中黑色方格只有1個，那麼下一時刻當前方格就是黑色；如果有兩個黑色方格，則下時刻是白色，如果有三個方格，則下時刻是黑色，如果有4個方格，那麼下一時刻是白色”可以表示成下面的函數表：

si,t+1=1，如果si-1,t+si,t+si+1,t=1

si,t+1=0，如果si-1,t+si,t+si+1,t=2

si,t+1=1，如果si-1,t+si,t+si+1,t=3

si,t+1=0，如果si-1,t+si,t+si+1,t=0

其中，si,t∈{0,1}，對於任意的i和t

這種情況下，輸入就僅僅有4種情況，因此可以得到下面的表：

同樣的道理，我們可以對它進行編碼為：0101，表示為十進位就是5。顯然，這種編碼方式比前一種短，但是這種編碼方法不能反映所有的細胞自動機。

（3）最簡一維細胞自動機的動態行為

對於一維的情況，我們假設所有的方格都分佈在一條直線上，並且直線的長度為我們動畫區域的寬度，比如說是400，也就是說有400個方格在這條直線上。我們用黑色的格表示直線上1狀態的方格，用白色的格表示0狀態的方格。那麼一條斷續的橫線就是當前所有細胞狀態的一種分佈。這些方格隨著時間變化，就形成了不同的橫線。我們把這些隨著時間變化的線縱向拼在一起形成了一個網格區域。其中縱軸表示時間的流逝（往下為正），橫軸為細胞自動機在對應時刻的狀態，就能得到一幅圖像。這就是上面的示常式序所表演的，變換不同的編碼參數，你會看到，觀察它們的動態行為。

在最簡細胞自動機的情況下（狀態數是2，半徑是1），這些細胞自動機分成3類。觀察224號（長編碼）細胞自動機，從上而下出現了一些細胞，之後就逐漸變成了全白色，也就是說經過幾個時間步的運行后，細胞自動機全部變為了固定狀態0（也就是白色的方格），並再也不變化了。而132號和203號細胞自動機都是變成了幾個豎線。不要忘了每一行就是某一時刻細胞自動機的一個狀態，因此在豎向上能夠形成一條豎線就說明這個細胞的狀態在時間軸上沒有變化。所以132號、203號與224號它們被吸引到了一個固定的狀態。

再看208號細胞自動機，它是若干條斜的線。由於我們的邊界是循環的，因此可以預言，經過若干個時間周期的運行以後，細胞自動機又回復到了原來的狀態，因而這樣的細胞自動機是循環的。兩個相同狀態之間經歷的時間步長為這種細胞自動機的周期。再看150號和151號細胞自動機，他們顯然既沒有固定的周期也沒有被吸引到一個點，它們是出於一種混亂的、無序的狀態，我們稱這種狀態為混沌狀態。通過反覆的運行最簡細胞自動機程序我們不難發現，所有的256種細胞自動機都能被歸為這三類：固定值、周期循環、混沌之一。

我們可以猜想，是不是所有的細胞自動機的動態行為就這三種類型呢？讓我們把探索的疆域擴大到稍微複雜一點的情況，我們考慮狀態數為2，鄰居半徑為2（也就是說每個細胞都有4個鄰居，左右兩邊各兩個），仍然是一維的情況。在這樣的細胞自動機中除了上面敘述的三種類別依然存在外，我們還發現了另一種類型，請看20號（按照短編碼方案）和52號（按照短編碼方案）這兩個細胞自動機的動態運行圖竟然如此怪異，就好像一棵倒掛的葡萄藤。這種葡萄藤是一種複雜的結構，它既不等同於完全的隨機，又沒有固定的循環的跡象。這種複雜結構正是我們感興趣的一種類型，因為它既沒有被吸引到固定的點或周期狀態而變得死板，又沒有因為隨機而過於活躍；它既保證了一定的流動活性，同時又能產生具有“記憶性”的結構。該運行情況顯然不同於前面敘述的三種類別，所以我們稱其為複雜型。繼續運行各種參數的一維細胞自動機，我們發現幾乎所有的一維細胞自動機運行的動態行為都能被劃分為這四類情況。

綜合上面的討論，我們把細胞自動機歸為四種類別，它們分別是：

I、固定值型：細胞自動機經過若干步運算便停留在一個固定的狀態；

II、周期型：細胞自動機在幾種狀態之間周期循環；

III、混沌型：細胞自動機處於一種完全無序隨機的狀態，幾乎找不到任何規律；

IV、複雜型：細胞自動機在運行的過程中可能產生複雜的結構，這種結構既不是完全的隨機混亂，又沒有固定的周期和狀態。

上面我們僅僅就一維細胞自動機的情況作了介紹，二維細胞自動機也無非就是這4種情況之一。其實我們想一下，前面介紹的“生命遊戲”屬於哪種類型呢？當然應該是第IV種。只有複雜的類型才會給我們帶來永恆的新奇。

細胞自動機不僅可以在形式上作為并行計算機的理論模型來研究，而且還可以作為語言（被機器接受的輸入字的集合）識別器。一個語言被某種識別器所識別是指：識別器不僅接受該語言中的字，而且拒絕不屬於該語言中的字。在維數高於1時，語言識別有時被看作模式識別。對於迭合自動機，如果每一時間步只輸入一個字母，當字全部輸完之後，如果輸入輸出細胞進入一個特別設計的接受狀態，就認為它接受了這個字。語言的所有的字都被接受時就稱為迭合自動機語言。類似地，棋盤格自動機和一維細胞自動機也可以用作語言接受器。

用細胞自動機的并行計算方式可實現一些并行計算機和識別器的設計。細胞自動機對於集成電路的設計方法具有重要意義。大規模集成電路採用細胞陣列形式具有明顯的優點。生物學推動了有關自動機的理論研究。反過來，有關自動機理論的發展為生物發育學提供了一種數學模型和方法。細胞自動機論的研究與形式語言的研究更是息息相關，各種細胞自動機的識別能力，以及它們所能識別的各種語言類與各類形式語言之間的關係都還處於探討中。另外，各種類型細胞自動機的性質，以及它們彼此之間的關係也都是人們關心的課題。