基本介紹
- 中文名：細胞自動機論
- 提出者：J.諾伊曼
發展進程,內容,諾伊曼細胞空間,棋盤格空間,迭合空間,射擊小分隊問題與蜂王問題,圖細胞自動機,動態細胞自動機,語言識別器,
發展進程
J.諾伊曼在50年代初期研究自生長自動機的邏輯問題時，是以細胞空間作為主要工具的。根據他提出的細胞空間概念已發展出許多研究方向。並行計算機的體系設計和大規模積體電路技術，都套用這些概念來研究具有一致結構的各種細胞自動機的分析、綜合和容錯等問題。1968年A.林頓梅伊爾推廣了諾伊曼的細胞空間概念，提出一種動態細胞自動機的數學結構──L系統，用以描述多細胞組織的發育過程。各種類型的細胞自動機都是由馮·諾依曼的細胞自動機推廣而來的。諾依曼細胞自動機是最早的、最基本的自動機。
內容
諾伊曼細胞空間
這種空間的形式像一個把行和列上的格子向上下左右無限擴展的無限棋盤。每一個格子都被看作是一個“細胞”，這些細胞都是相同的，具有29狀態的確定的有限自動機，並假定都是在相同時刻改變自己的狀態，即它們的動作在時間上是同步的。每個細胞和它的上下左右直接相鄰的細胞構成它的一個鄰域，它在時刻t+1的狀態,由它的鄰域中各個有限自動機在時刻 t的狀態決定。有一個特殊的狀態S0叫作靜止狀態。當細胞的鄰域中的狀態都是S0時，它的下一時刻的狀態仍是S0，並且假定除了有限個細胞外，所有其餘的細胞都處於這種狀態。因而，儘管細胞空間是無限的，但在任何時刻人們只注意其中有限個。對細胞空間的每一個細胞賦予一個狀態，並且保持其狀態不是S0的細胞的個數為有限個,這種賦值叫作細胞空間的一個構形。在時刻t=0的構形叫作初始構形。細胞空間以外的事物或信息只能在這個時刻對它起作用。在時刻t=0之後,構形的所有改變都按預先給定的規則自主地進行,即在t=0後不再有外來輸入。初始構形完全決定以後各個時刻的構形，並且在每一（時間）步上只能改變一次。構形內的非靜止狀態細胞的集合叫作構形的支架。在前面所說的情況下，支架當然是有限集合。有限的細胞空間即稱為細胞自動機。
諾伊曼細胞空間的所有細胞都在整數格線的結點上，細胞個數為無限。它滿足下列條件：各個細胞都是確定的摩爾型有限自動機；採取五鄰域一致連線模式（所有細胞有同樣形狀的鄰域）；不帶外部輸入，不向外部輸出；並且是靜態的（鄰域不隨時間改變）。一般的細胞空間不必要這些條件限制，故此外還有非確定型細胞空間、米雷型細胞空間、連線模式非一致的細胞空間、帶外部輸入的細胞空間以及動態的細胞空間等。
棋盤格空間
細胞空間的一個直接推廣。它有分配到各個細胞的統一的外部輸入。或者說，棋盤格空間是一個程式控制的細胞空間。棋盤格空間裡的每一個細胞能夠被想像為有一個局部轉移函式的有限集合。因此，棋盤格空間有一個全局轉移函式的有限集合。程式中的各個“指令”選擇在該時刻的轉移中所使用的全局轉移函式。
迭合空間
對細胞空間的一個細胞給定一個外部輸入和外部輸出，這個特定的細胞叫作“輸入輸出細胞”。這個細胞空間也就叫作迭合空間。
射擊小分隊問題與蜂王問題
細胞自動機理論中著名問題之一是射擊小分隊問題。在這個問題中，把各個細胞看作戰士，其中一個當隊長。開始時，除了作隊長的細胞之外，所有其餘細胞都處於靜止狀態，然後隊長下令“開火”。問題是是否所有戰士都能同時射擊，即同時進入同一狀態。射擊小分隊定理對這個問題給以肯定的答案。這個定理在非一致連線模式的情況下也成立。與此結果密切相關的另一結果是蜂王定理。它解決與射擊小分隊定理相反的問題，即要求設計一個細胞自動機使得所有狀態開始時都處於同一個狀態，最後有一個且只有一個細胞很快地被作為接受細胞──蜂王──標明出來。
圖細胞自動機
僅要求鄰域內細胞個數固定，而不要求這些細胞之間有任何固定的幾何關係。這類細胞自動機比一致連線的細胞自動機更強有力。
動態細胞自動機
在這類細胞自動機中，不管細胞在初始細胞陣列中的位置如何，允許細胞分裂成為兒女細胞，並且允許細胞消亡。理論生物學家對這一類型自動機很感興趣，把它當作為有生命物的發育模型。
語言識別器
細胞自動機不僅可以在形式上作為並行計算機的理論模型來研究，而且還可以作為語言（被機器接受的輸入字的集合）識別器。一個語言被某種識別器所識別是指：識別器不僅接受該語言中的字，而且拒絕不屬於該語言中的字。在維數高於1時,語言識別有時被看作模式識別。對於迭合自動機，如果每一(時間)步只輸入一個字母，當字全部輸完之後，如果輸入輸出細胞進入一個特別設計的接受狀態，就認為它接受了這個字。語言的所有的字都被接受時就稱為迭合自動機語言。類似地，棋盤格自動機和一維細胞自動機也可以用作語言接受器。
用細胞自動機的並行計算方式可實現一些並行計算機和識別器的設計。細胞自動機對於積體電路的設計方法具有重要意義。大規模積體電路採用細胞陣列形式具有明顯的優點。生物學推動了有關自動機的理論研究。反過來，有關自動機理論的發展為生物發育學提供了一種數學模型和方法。細胞自動機論的研究與形式語言的研究更是息息相關，各種細胞自動機的識別能力，以及它們所能識別的各種語言類與各類形式語言之間的關係都還處於探討中。另外,各種類型細胞自動機的性質,以及它們彼此之間的關係也都是人們關心的課題。
