一種機械結構，它具有通用性，放入什麼初始結構，都能夠得到他的複製品，甚至還有計算的性質。
基本介紹
- 中文名：自複製自動機
- 外文名：Since the replication automata
- 提出時間：1948年
- 創始人：John von Neumann
概述,發展歷程,自我複製元胞自動機模型,Von Neumann的模型,Codd的模型,Vitanyi模型,Langton的自我複製環,
概述
元胞自動機的涉及到的範圍很廣，包含很多複雜的現象的模擬，比如晶體的生長，化學反應形成的斑圖等。其中，有一種形式的元胞自動機，意在揭示生命的出現和繁衍的邏輯，它不考慮物理上如何構造一個生命系統，而是希望在邏輯上實現自我複製或繁衍的行為。如果把世界看成機器，那我們所要找的就是在機器世界中生物映射成什麼，和一種達成這個映射的算法。這就是自我複製的元胞自動機。
簡單地說，自我複製系統是一種能夠依據自身所攜帶的信息來指導它們自己進行複製的系統，它的複製過程不需要外界來干預。自然界中自我複製系統的例子是各種生命系統。在元胞自動機空間中，自我複製結構是由活躍(非靜止)元胞所構成的斑圖，其形成只依賴元胞局部相互作用的規則和自組織行為。複製過程由結構本身的中心控制程式控制，也就是“基因組”，這與生物體極為相似。對自我複製結構的深度探索，已經形成一個新的領域，即“人工生命”。
發展歷程
John von Neumann在提出一種自我複製的元胞自動機, 1948年，他首先開始構造這種自動機，或者說是一種機械結構，它具有通用性，即無論在原湯里(產生生命的海洋)放入什麼初始結構，都能夠得到他的複製品，甚至還有計算的性質。
在Ulam的建議下，他考慮用格子把空間離散化。這種離散後的格子就是元胞。他所設計的元胞自動機具有通用構造和計算的性質，並且是一種自我複製結構。他用到將近200000個元胞，直到1995年，U. Pesavento 才第一次在計算機上實現這種自動機。然而，他完成了自我複製自動機的邏輯設計，同時也實現了通用Turing機器。
1957年，John von Neumann逝世以後，Arthur W. Burks把他的關於元胞自動機通用構造器的細節整理成書。在書中指出VonNeumann證明了存在自我複製的自動機，並且存在通用構造器或通用計算機，他的元胞具有29個狀態。
後來，Burks的學生Codd詳細給出了構成自我複製自動機的組件，其中有著名的數據通道，T-型發射器和周期發射器等，這些為後來的Langton發現自我複製元胞自動機鋪平了道路。他把元胞的狀態數減少到8個，儘管元胞總數已經達到100,000,000個，但其複雜性已經比John von Neumann的機器降低許多，並且能夠實現與其相似的功能。
1984年，Langton以放棄計算性和通用性為代價，給出了一個真正實現自我複製的元胞自動機。
1990年，Langton在繼他的自我複製元胞自動機之後，研究元胞自動機計算的性質，他發現，混沌邊緣的相變現象與計算的特性——即傳播、存儲和修改信息——非常相似。
自我複製元胞自動機模型
Von Neumann的模型
它是一種通用構造器，能夠構造出任何一種置於CA空間中的構型。它在29狀態，5鄰居的元胞空間上展開，並採用弱旋轉對稱的規則。弱旋轉對稱是指，在二維坐標系內，元胞狀態連續旋轉若干個90度所得到的狀態排列也是此元胞具有的狀態。這種自動機由四部分組成:信息帶，信息帶控制器，構建控制器，構建臂。
信息帶上包含對所要構建的機器的描述，它分為兩部分，一部分是需要翻譯的信息，這部分信息指導複製的過程，另一部分信息是不需要翻譯的數據，它們直接被複製到新的機器當中;信息帶控制器閱讀信息帶上的信息，並將其翻譯成其具有相應作用的信號;構建控制器把得到的信號輸送到構建臂;構建臂在CA空間中延伸，建造需要建造的機器。當向一架機器提供已經編好信息的信息帶之後，按下“開始”的按鈕，就開始了複製的過程。步驟如下:
閱讀輸入信息帶上的內容，將需要翻譯成指令的信息翻譯出來，指導複製過程的進行;
在靜止的元胞空間上構建我們需要的機器;
將信息帶翻過來，複製它自己;把信息帶的複製品附到新構建的機器上;
發信號示意新完成的部分;
撤回構建臂。
Codd的模型
Codd給出了一個更簡單的通用構造器，它在8狀態，5鄰居的二維CA空間上展開，並採用強旋轉對稱的規則。強旋轉對稱是指，空間均勻離散(除了自身的狀態之外，所有元胞都完全相同)，並且各向同性(不區分各個方向)，元胞的狀態本身也是沒有方向性的。這種自動機由100,000,000個元胞組成，並且是以帶鞘的數據通道為基礎。它能夠實現與Von Neumann的模型相似的功能。
Vitanyi模型
這個模型是元胞自動機有性個體複製的一個例子，它包含雄性類型和雌性類型的自動機。它也是在8狀態，5鄰居的二維CA空間上展開，兩個結構需要成千上萬的元胞。在從無性複製到有性複製的轉變中，信息帶的結構和數目將發生變化。這兩個自動機都包含兩個幾乎完全相同的信息帶。儘管這種自動機結構很複雜，這個模型也展示了自動機有性複製的可能性，並且這種過程與自然界的情形有些相似。
Langton的自我複製環
以上這些模型似乎都表明自我複製是一種內在的複雜現象。它們要求結構滿足通用構造性。然而，Langton發現，保留通用構造性對於複製結構不是必需的。有這樣的一種複製，它是基於物理機制，而不是依靠結構自身所攜帶的信息複製出自己。比如CA空間中的一個元胞，其狀態為“活”，其它為“死”，在5鄰居相關下，一段時間後，五個互不相連的元胞狀態為“活”。
