[科普中国]-自复制自动机-

概述

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

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

发展历程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在继他的自我复制元胞自动机之后，研究元胞自动机计算的性质，他发现，混沌边缘的相变现象与计算的特性——即传播、存储和修改信息——非常相似。1

自我复制元胞自动机模型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邻居相关下，一段时间后，五个互不相连的元胞状态为“活”。1