自复制自动机

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邻居相关下，一段时间后，五个互不相连的元胞状态为“活”。

元胞自动机的涉及到的范围很广，包含很多复杂的现象的模拟，比如晶体的生长，化学反应形成的斑图等。其中，有一种形式的元胞自动机，意在揭示生命的出现和繁衍的逻辑，它不考虑物理上如何构造一个生命系统，而是希望在逻辑上实现自我复制或繁衍的行为。如果把世界看成机器，那我们所要找的就是在机器世界中生物映射成什么，和一种达成这个映射的算法。这就是自我复制的元胞自动机。

简单地说，自我复制系统是一种能够依据自身所携带的信息来指导它们自己进行复制的系统，它的复制过程不需要外界来干预。自然界中自我复制系统的例子是各种生命系统。在元胞自动机空间中，自我复制结构是由活跃(非静止)元胞所构成的斑图，其形成只依赖元胞局部相互作用的规则和自组织行为。复制过程由结构本身的中心控制程序控制，也就是“基因组”，这与生物体极为相似。对自我复制结构的深度探索，已经形成一个新的领域，即“人工生命”。

自动机是有限状态机(FSM)的数学模型。

FSM 是给定符号输入，依据(可表达为一个表格的)转移函数“跳转”过一系列状态的一种机器。在常见的 FSM 的“Mealy”变体中，这个转移函数告诉自动机给定当前状态和当前字符的时候下一个状态是什么。

逐个读取输入中的符号，直到被完全耗尽(把它当作有一个字写在其上的磁带，通过自动机的读磁头来读取它；磁头在磁带上前行移动，一次读一个符号)。一旦输入被耗尽，自动机被称为“停止”了。

依赖自动机停止时的状态，称呼这个自动机要么是“接受”要么“拒绝”这个输入。如果停止于“接受状态”，则自动机“接受”了这个字。在另一方面，如果它停止于“拒绝状态”，则这个字被“拒绝”。自动机接受的所有字的集合被称为“这个自动机接受的语言”。

自动机 automaton 原来是模仿人和动物的行动而做成的机器人的意思。但是现已被抽象化为如下的机器。时间是离散的（t=0，1，2……），在每一个时刻它处于所存在的有限个内部状态中的一个。对每一个时刻给予有限个输入中的一个。那么下一个时刻的内部状态就由现在的输入和现在的内部状态所决定。每个时刻的输出只由那个时刻的内部状态所决定。作为自动机的例子可以举出由McCulloch-pitts的神经模型组合所得到的神经网络模型、数字计算机等。

上述自动机接受的语言家族被称为正规语言(Regular Expression)。更强力的自动机可以接受更复杂的语言。比如:

自动机PDA

PDA(下推自动机)这种机器等同于 DFA (或 NFA)，除了它们额外的装备了栈形式的内存。转移函数 δ 也依赖于在栈顶的符号，并在每次转移时指定如何变更栈。非确定 PDA 接受上下文无关语言。

自动机LBA

LBA （线性有界自动机）是有限制的 图灵机；不使用无限磁带，它的磁带有同输入字元串成正比的空间。LBA 接受上下文有关语言。

自动机图灵机

它们是最强力的电脑器。它们拥有磁带形式的无限内存，和可以读取和变更磁带的磁头，它可在磁带上向任何方向移动。图灵机等价于演算法，是现代电脑的理论基础。图灵机判定递归语言并识别递归可枚举语言。

下面是三类有限自动机

确定有限自动机(DFA)

自动机的每个状态都有对字母表中所有符号的转移。

非确定有限自动机(NFA)

自动机的状态对字母表中的每个符号可以有也可以没有转移，对一个符号甚至可以有多个转移。自动机接受一个字，如果存在至少一个从 q0 到 F 中标记(label)著这个输入字的一个状态的路径。如果一个转移是「未定义」的，自动机因此不知道如何继续读取输入，则拒绝这个字。

有ε转移的非确定有限自动机(FND-ε或ε-NFA)

除了有能力对任何符号跳转到更多状态或没有状态可以跳转之外，它们可以做根本不关于符号的跳转。就是说，如果一个状态有标记著 ε 的转移，则 NFA 可以处在 ε-转移可到达的任何状态中，直接或通过其他有 ε-转移的状态。从一个状态 q 通过这种方法可到达的状态的集合叫做 q 的 ε-闭包。

尽管可以证明所有这些自动机都「可以接受同样的语言」。你总是可以构造接受与给定的 NFA M 同样语言的某个 DFA M。