自復(fù)制自動機

John von Neumann在提出一種自我復(fù)制的元胞自動機, 1948年，他首先開始構(gòu)造這種自動機，或者說是一種機械結(jié)構(gòu)，它具有通用性，即無論在原湯里(產(chǎn)生生命的海洋)放入什么初始結(jié)構(gòu)，都能夠得到他的復(fù)制品，甚至還有計算的性質(zhì)。

在Ulam的建議下，他考慮用格子把空間離散化。這種離散后的格子就是元胞。他所設(shè)計的元胞自動機具有通用構(gòu)造和計算的性質(zhì)，并且是一種自我復(fù)制結(jié)構(gòu)。他用到將近200000個元胞，直到1995年，U. Pesavento 才第一次在計算機上實現(xiàn)這種自動機。然而，他完成了自我復(fù)制自動機的邏輯設(shè)計，同時也實現(xiàn)了通用Turing機器。

1957年，John von Neumann逝世以后，Arthur W. Burks把他的關(guān)于元胞自動機通用構(gòu)造器的細(xì)節(jié)整理成書。在書中指出VonNeumann證明了存在自我復(fù)制的自動機，并且存在通用構(gòu)造器或通用計算機，他的元胞具有29個狀態(tài)。

后來，Burks的學(xué)生Codd詳細(xì)給出了構(gòu)成自我復(fù)制自動機的組件，其中有著名的數(shù)據(jù)通道，T-型發(fā)射器和周期發(fā)射器等，這些為后來的Langton發(fā)現(xiàn)自我復(fù)制元胞自動機鋪平了道路。他把元胞的狀態(tài)數(shù)減少到8個，盡管元胞總數(shù)已經(jīng)達(dá)到100,000,000個，但其復(fù)雜性已經(jīng)比John von Neumann的機器降低許多，并且能夠?qū)崿F(xiàn)與其相似的功能。

1984年，Langton以放棄計算性和通用性為代價，給出了一個真正實現(xiàn)自我復(fù)制的元胞自動機。

1990年，Langton在繼他的自我復(fù)制元胞自動機之后，研究元胞自動機計算的性質(zhì)，他發(fā)現(xiàn)，混沌邊緣的相變現(xiàn)象與計算的特性——即傳播、存儲和修改信息——非常相似。

自復(fù)制自動機Von Neumann的模型

它是一種通用構(gòu)造器，能夠構(gòu)造出任何一種置于CA空間中的構(gòu)型。它在29狀態(tài)，5鄰居的元胞空間上展開，并采用弱旋轉(zhuǎn)對稱的規(guī)則。弱旋轉(zhuǎn)對稱是指，在二維坐標(biāo)系內(nèi)，元胞狀態(tài)連續(xù)旋轉(zhuǎn)若干個90度所得到的狀態(tài)排列也是此元胞具有的狀態(tài)。這種自動機由四部分組成:信息帶，信息帶控制器，構(gòu)建控制器，構(gòu)建臂。

信息帶上包含對所要構(gòu)建的機器的描述，它分為兩部分，一部分是需要翻譯的信息，這部分信息指導(dǎo)復(fù)制的過程，另一部分信息是不需要翻譯的數(shù)據(jù)，它們直接被復(fù)制到新的機器當(dāng)中;信息帶控制器閱讀信息帶上的信息，并將其翻譯成其具有相應(yīng)作用的信號;構(gòu)建控制器把得到的信號輸送到構(gòu)建臂;構(gòu)建臂在CA空間中延伸，建造需要建造的機器。當(dāng)向一架機器提供已經(jīng)編好信息的信息帶之后，按下“開始”的按鈕，就開始了復(fù)制的過程。步驟如下:

閱讀輸入信息帶上的內(nèi)容，將需要翻譯成指令的信息翻譯出來，指導(dǎo)復(fù)制過程的進(jìn)行;

在靜止的元胞空間上構(gòu)建我們需要的機器;

將信息帶翻過來，復(fù)制它自己;把信息帶的復(fù)制品附到新構(gòu)建的機器上;

發(fā)信號示意新完成的部分;

撤回構(gòu)建臂。

自復(fù)制自動機Codd的模型

Codd給出了一個更簡單的通用構(gòu)造器，它在8狀態(tài)，5鄰居的二維CA空間上展開，并采用強旋轉(zhuǎn)對稱的規(guī)則。強旋轉(zhuǎn)對稱是指，空間均勻離散(除了自身的狀態(tài)之外，所有元胞都完全相同)，并且各向同性(不區(qū)分各個方向)，元胞的狀態(tài)本身也是沒有方向性的。這種自動機由100,000,000個元胞組成，并且是以帶鞘的數(shù)據(jù)通道為基礎(chǔ)。它能夠?qū)崿F(xiàn)與Von Neumann的模型相似的功能。

自復(fù)制自動機Vitanyi模型

這個模型是元胞自動機有性個體復(fù)制的一個例子，它包含雄性類型和雌性類型的自動機。它也是在8狀態(tài)，5鄰居的二維CA空間上展開，兩個結(jié)構(gòu)需要成千上萬的元胞。在從無性復(fù)制到有性復(fù)制的轉(zhuǎn)變中，信息帶的結(jié)構(gòu)和數(shù)目將發(fā)生變化。這兩個自動機都包含兩個幾乎完全相同的信息帶。盡管這種自動機結(jié)構(gòu)很復(fù)雜，這個模型也展示了自動機有性復(fù)制的可能性，并且這種過程與自然界的情形有些相似。

自復(fù)制自動機Langton的自我復(fù)制環(huán)

以上這些模型似乎都表明自我復(fù)制是一種內(nèi)在的復(fù)雜現(xiàn)象。它們要求結(jié)構(gòu)滿足通用構(gòu)造性。然而，Langton發(fā)現(xiàn)，保留通用構(gòu)造性對于復(fù)制結(jié)構(gòu)不是必需的。有這樣的一種復(fù)制，它是基于物理機制，而不是依靠結(jié)構(gòu)自身所攜帶的信息復(fù)制出自己。比如CA空間中的一個元胞，其狀態(tài)為“活”，其它為“死”，在5鄰居相關(guān)下，一段時間后，五個互不相連的元胞狀態(tài)為“活”。

元胞自動機的涉及到的范圍很廣，包含很多復(fù)雜的現(xiàn)象的模擬，比如晶體的生長，化學(xué)反應(yīng)形成的斑圖等。其中，有一種形式的元胞自動機，意在揭示生命的出現(xiàn)和繁衍的邏輯，它不考慮物理上如何構(gòu)造一個生命系統(tǒng)，而是希望在邏輯上實現(xiàn)自我復(fù)制或繁衍的行為。如果把世界看成機器，那我們所要找的就是在機器世界中生物映射成什么，和一種達(dá)成這個映射的算法。這就是自我復(fù)制的元胞自動機。

簡單地說，自我復(fù)制系統(tǒng)是一種能夠依據(jù)自身所攜帶的信息來指導(dǎo)它們自己進(jìn)行復(fù)制的系統(tǒng)，它的復(fù)制過程不需要外界來干預(yù)。自然界中自我復(fù)制系統(tǒng)的例子是各種生命系統(tǒng)。在元胞自動機空間中，自我復(fù)制結(jié)構(gòu)是由活躍(非靜止)元胞所構(gòu)成的斑圖，其形成只依賴元胞局部相互作用的規(guī)則和自組織行為。復(fù)制過程由結(jié)構(gòu)本身的中心控制程序控制，也就是“基因組”，這與生物體極為相似。對自我復(fù)制結(jié)構(gòu)的深度探索，已經(jīng)形成一個新的領(lǐng)域，即“人工生命”。

自動機是有限狀態(tài)機(FSM)的數(shù)學(xué)模型。

FSM 是給定符號輸入，依據(jù)(可表達(dá)為一個表格的)轉(zhuǎn)移函數(shù)“跳轉(zhuǎn)”過一系列狀態(tài)的一種機器。在常見的 FSM 的“Mealy”變體中，這個轉(zhuǎn)移函數(shù)告訴自動機給定當(dāng)前狀態(tài)和當(dāng)前字符的時候下一個狀態(tài)是什么。

逐個讀取輸入中的符號，直到被完全耗盡(把它當(dāng)作有一個字寫在其上的磁帶，通過自動機的讀磁頭來讀取它；磁頭在磁帶上前行移動，一次讀一個符號)。一旦輸入被耗盡，自動機被稱為“停止”了。

依賴自動機停止時的狀態(tài)，稱呼這個自動機要么是“接受”要么“拒絕”這個輸入。如果停止于“接受狀態(tài)”，則自動機“接受”了這個字。在另一方面，如果它停止于“拒絕狀態(tài)”，則這個字被“拒絕”。自動機接受的所有字的集合被稱為“這個自動機接受的語言”。

自動機 automaton 原來是模仿人和動物的行動而做成的機器人的意思。但是現(xiàn)已被抽象化為如下的機器。時間是離散的（t=0，1，2……），在每一個時刻它處于所存在的有限個內(nèi)部狀態(tài)中的一個。對每一個時刻給予有限個輸入中的一個。那么下一個時刻的內(nèi)部狀態(tài)就由現(xiàn)在的輸入和現(xiàn)在的內(nèi)部狀態(tài)所決定。每個時刻的輸出只由那個時刻的內(nèi)部狀態(tài)所決定。作為自動機的例子可以舉出由McCulloch-pitts的神經(jīng)模型組合所得到的神經(jīng)網(wǎng)絡(luò)模型、數(shù)字計算機等。

上述自動機接受的語言家族被稱為正規(guī)語言(Regular Expression)。更強力的自動機可以接受更復(fù)雜的語言。比如:

自動機PDA

PDA(下推自動機)這種機器等同于 DFA (或 NFA)，除了它們額外的裝備了棧形式的內(nèi)存。轉(zhuǎn)移函數(shù) δ 也依賴于在棧頂?shù)姆?，并在每次轉(zhuǎn)移時指定如何變更棧。非確定 PDA 接受上下文無關(guān)語言。

自動機LBA

LBA （線性有界自動機）是有限制的 圖靈機；不使用無限磁帶，它的磁帶有同輸入字元串成正比的空間。LBA 接受上下文有關(guān)語言。

自動機圖靈機

它們是最強力的電腦器。它們擁有磁帶形式的無限內(nèi)存，和可以讀取和變更磁帶的磁頭，它可在磁帶上向任何方向移動。圖靈機等價于演算法，是現(xiàn)代電腦的理論基礎(chǔ)。圖靈機判定遞歸語言并識別遞歸可枚舉語言。

下面是三類有限自動機

確定有限自動機(DFA)

自動機的每個狀態(tài)都有對字母表中所有符號的轉(zhuǎn)移。

非確定有限自動機(NFA)

自動機的狀態(tài)對字母表中的每個符號可以有也可以沒有轉(zhuǎn)移，對一個符號甚至可以有多個轉(zhuǎn)移。自動機接受一個字，如果存在至少一個從 q0 到 F 中標(biāo)記(label)著這個輸入字的一個狀態(tài)的路徑。如果一個轉(zhuǎn)移是「未定義」的，自動機因此不知道如何繼續(xù)讀取輸入，則拒絕這個字。

有ε轉(zhuǎn)移的非確定有限自動機(FND-ε或ε-NFA)

除了有能力對任何符號跳轉(zhuǎn)到更多狀態(tài)或沒有狀態(tài)可以跳轉(zhuǎn)之外，它們可以做根本不關(guān)于符號的跳轉(zhuǎn)。就是說，如果一個狀態(tài)有標(biāo)記著 ε 的轉(zhuǎn)移，則 NFA 可以處在 ε-轉(zhuǎn)移可到達(dá)的任何狀態(tài)中，直接或通過其他有 ε-轉(zhuǎn)移的狀態(tài)。從一個狀態(tài) q 通過這種方法可到達(dá)的狀態(tài)的集合叫做 q 的 ε-閉包。

盡管可以證明所有這些自動機都「可以接受同樣的語言」。你總是可以構(gòu)造接受與給定的 NFA M 同樣語言的某個 DFA M。