第8章 自我复制的计算机程序

生命是什么

第5章介绍了一些生命进化的思想史。但是有一些问题没有提到，例如生命是如何起源的？生命的要素到底是什么？这些都是科学界最具争议的问题，至今没有确定的答案。在这里我不讨论前一个问题，不过复杂系统对此有一些让人着迷的研究。

生命到底是什么，这是一个经久不衰的问题。不管是大众还是科学家，对此都没有达成共识。像“生命是如何诞生的”或者“生命在其他星球上是什么样子”总是能激起热烈的讨论，甚至引起敌意。

创造人工生命的想法也由来已久，至少可以追溯到两千年前的石人传说（Golem）和奥维德（Ovid）的皮格马利翁，19世纪又有福兰克斯坦的怪兽（Frankenstein’s monster）的故事，更不要说现在的《刀锋战士》和《黑客帝国》这些影片，以及《模拟生命》（Sim Life）这类计算机游戏。

科幻作品提出了一个新版本的“生命是什么”的问题：计算机和机器人可以被认为有生命吗？这个问题将计算、生命和进化的问题联系到一起。

如果你问10个生物学家什么是生命的10个要素，每次得到的答案都会不一样。可能大部分会包括自主、新陈代谢、自我复制、生存本能，还有进化和适应。我们能不能将这些过程机械化，并用计算机来实现呢？

许多人认为绝对不可能，理由如下：

自主：计算机本身什么都做不了；只能执行程序的指令。

新陈代谢：计算机无法像生物那样从环境中获取能量；它们必须由人提供能源（例如电力）。

自我复制：计算机不能复制自身；要复制自身就必须包含对自身的描述；而这个描述又包含其本身的描述，这样反复无穷。

生存本能：计算机不关心自己能不能生存，它们也不关心自己是不是成功。（有一次听一位杰出的心理学家的讲座，他在谈论计算机象棋程序时说：“就算深蓝赢了卡斯帕罗夫，它也不会有快乐的感觉。”）

进化和适应：计算机本身无法进化或适应；它只能严格依照程序员预先设定的方式变化。

虽然还有很多人相信这些观点，但它们都在人工生命领域中以各种方式被否定了。人工生命关注的是在计算机中仿真或“创造”生命。在这一章和下一章我会讨论这些，它们与达尔文主义的自我复制和进化密切相关。

计算机中的自我复制

自我复制的观点非常数学化：它认为计算机中的自我复制会导致无穷反复。

我们先来看看计算机自我复制问题最简单的形式：写一段程序打印其自身。

在后面我们用一种简单的计算机语言，这样不用是程序员也能看懂。（实际上是一种伪代码，有一些真正的计算机语言所没有的命令，但是是合理的，只是让事情更简单一些。）

下面来试一下，首先从程序的名字开始：

program copy

然后加一条指令将程序的名字打印出来：

program copy

print（“program copy”）

指令print只是简单地将引号之间的字符显示到屏幕上然后换行。现在增加一条指令将第二行打印出来：

program copy

print（“program copy”）

print（“print（“program copy”）”）

因为要输出程序自身的完整复制，第二个print指令的引号中带了第一个print指令前的四个缩进符和后面的一对引号（print指令输出最外侧的引号之间的所有字符，包括引号）。现在又要加一条指令来输出第三行：

program copy

print（“program copy”）

print（“print（“program copy”）”）

print（“print（“print（“program copy”）”）”）

现在你可能已经看出来，这种策略——每条指令输出上一条指令的拷贝——是如何导致无穷反复的。怎样才能避免这种情况呢？在继续往下读之前，你可以花点时间自己试一试能不能解决这个问题。

这个看似简单的问题其实关系到第4章介绍过的哥德尔和图灵的工作。解决方法同时也包含了生物系统本身绕开无穷反复的基本途径。20世纪匈牙利数学家冯·诺依曼在研究一个更复杂的问题时，首先发现了这个问题的答案。

冯·诺依曼是量子力学、经济学等多个领域的先驱，也是最早设计电子计算机的人之一。他的设计中包含中央处理单元和可以存储程序和数据的随机存取存储器。这些至今仍然是现代计算机的基础。冯·诺依曼也是最早深刻认识到计算和生物之间联系的科学家之一。他在生命最后的岁月里一直致力于解决机器如何才能复制自身的问题。他给出了第一个能自我复制的机器的完整设计。我在后面展示的自复制计算机程序就是受他的“自复制自动机”启发，并以简化的方式阐释其基本原则。

在介绍自复制程序之前，还要先解释一些会用到的编程语言的相关知识。

参考图8.1给出的计算机存储器示意图。在我们高度简化的例子中，计算机存储器由有编号的位置或“地址”组成，图中编号为1—5，依次往后。各位置中有一些字符。这些字符可以作为程序的指令或程序使用的数据。如果执行当前存储的程序，会显示输出：

Hello, world！

Goodbye.

要执行程序，计算机要有一个“指令指针”——同样存储在存储器中的一个数字，记录当前执行的指令在存储器中的位置。指令指针——简记为ip——最初设为程序第一行的存储地址。我们称之为“指向”那条指令。在计算的每一步ip指向的指令会被执行，ip加1。

例如，在图8.1中，ip的值为2，也就是说指向的是print（“Hello, world！”）。

我们称ip为变量，因它的值随着计算的进行而不断变化。

还可以定义变量line[n]表示地址n中的字符串。例如，指令print（line[2]）会显示输出：

（“Hello, world！”）

此外，我们的编程语言中还包括loop指令（循环）。例如，下面的程序代码：

x=0

loop until x=4

{

print（“Hello, world！”）

x=x+1

}

会输出：

Hello, world！

Hello, world！

Hello, world！

Hello, world！

大括号之间的代码会反复执行直到循环结束条件（这里是x=4）满足。变量用作计数器——从0开始，每循环一次加1。增加到4时循环停止。

现在可以来看看自我复制程序了，程序完整展现在图8.2中。理解一段程序最好的办法就是手工推演，也就是一行一行跟踪程序的运行。

假设图8.2中的程序被加载到内存中，然后假设有人在计算机命令提示符后键入selfcopy，计算机就会开始执行程序selfcopy。译码器——操作系统的一部分——会将指令指针设为1，指向程序名。然后ip会下移，逐行执行各条指令。

在地址2处变量L被设为ip-1。而ip是当前执行指令的位置。因此当执行第2行时，ip设为2，L设为2-1=1。（注意虽然随着指令执行会不断变化，但L在重置之前会一直等于1直到其被重置。）接着会进入循环，直到line[L]等于字符串end。前面说了line[L]等于内存中地址L处的字符串。目前L等于1，line[L]等于字符串programselfcopy，不等于字符串end，因此循环不会停止。在循环中，会显示输出line[L]，并将L加1。最初，L=1，显示输出program selfcopy；然后L被置为2。

现在，line[L]指的是程序第二行，即L=ip-1，仍然不等于end，因此循环会继续。这样程序就会被逐行输出。尤其有意思的是第5行：当L=5时，执行第5行，指令print（line[L]）会显示输出其自身。当L=9时，line[L]等于end，循环终止。这时已经显示输出了1—8行。指令指针指向第8行（紧跟在循环后面的指令），执行时显示输出字符串“end”结束自我复制。在这个程序中自我复制的本质，是用两种方式来使用内存中的信息：既作为执行的指令，又作为这些指令使用的数据。正是对信息的双重使用让我们得以避开前面尝试自我复制程序时遇到的那种无穷反复。

自我复制程序的深层意义

信息的双重使用是哥德尔悖论的核心，他的自指句子“这个命题是不可证的”体现的正是这一点。

理解这个需要耍点把戏。首先，请注意这个句子同其他句子一样，可以从两个角度来看：①视为句子中包括的文字、空格符和标点组成的字符串；②视为字符串所代表的意义，同语言使用者的解读一样。

为了明确起见，我们将句子的字符串本身记为S。也就是说，S=“这个命题是不可证的”。现在可以陈述的一些命题：例如它包含9个字，1个句号。

句子的意义则记为M。我们可以将M重写为“命题S是不可证的”。某种程度上，你可以将M视为“指令”，而将S视为指令操作的数据。怪异（而又神奇）的是，数据S与指令M是同一个东西。哥德尔之所以能将句子转化为数学中的悖论，一个主要原因就是他能将M表示成数学命题，将S表示成编码那个数学命题字符串的数字。

这就是背后的把戏。侯世达在《哥德尔、艾舍尔、巴赫——集异璧之大成》一书中，对字符串与字符串的意义之间的区别，以及自指所导致的悖论，进行了详细而有趣的讨论。

与之类似，对信息的双重使用也是图灵对停机问题不可判定性证明的关键。还记得第4章的H和H′吗？记得H′是如何作用于自身的编码吗？同这里的自复制程序一样，H′也是以两种方式被使用：解释为程序，同时也作为程序的输入。

DNA的自我复制

现在你可能在想，我们又回到了让人头痛的抽象逻辑王国。别急，我们马上就会回到现实世界。真正让人惊奇的是对信息的双重使用竟然也是DNA复制自身的关键。在第6章我们了解到，DNA是由核苷酸序列组成。特定的子序列（基因）编码构成蛋白质的氨基酸，其中包括解开双螺旋和用信使RNA、转运RNA、核糖体等复制各股DNA的酶（特定种类的蛋白质）。作一个宽泛的类比，对执行复制的酶进行编码的DNA序列大致上对应于自复制程序的代码。这些DNA中的“代码”在产生酶和作用于DNA自身时就相当于被执行，DNA本身则相当于被解开和复制的数据。

不过你可能已经注意到了我埋下的伏笔。在自复制程序和DNA的自复制之间有一个重要的差别。自复制程序需要有一个解释器来执行它：指令指针依次指向各行代码，然后由操作系统来执行它们（存取ip和L等中间变量，显示输出字符串，等等）。执行器完全外在于程序本身。

而在DNA的情形中，构建“解释器”——信使RNA、转运RNA，核糖体和所有用于蛋白质合成的成分——的指令也一起编码在DNA中。也就是说，DNA不仅包含自我复制的“程序”（例如用来解开和复制DNA的酶），同时也编码了它自己的解释器（将DNA转译成酶的细胞器）。

冯·诺依曼的自复制自动机

冯·诺依曼最初的自复制自动机（冯·诺依曼只给出了数学描述，并没有真的建造）也是既包含有自我复制的程序也包含解释自身程序的机制。因此是完整的自我复制机器。这也解释了为何冯·诺依曼的构想要比我的自我复制程序复杂得多。冯·诺依曼提出构想是在20世纪50年代，当时生物自我复制的机制还没有被完全理解，这更加表明了冯·诺依曼天才的洞察力。冯·诺依曼对自动机的设计以及其正确性的数学证明在他去世前已基本完成。1957年，他因癌症去世，年仅53岁，可能是因为在参与研制原子弹时受到了核辐射。冯·诺依曼的同事巴克斯（Arthur Burks）完成了最后的证明。1966年，巴克斯将全部成果编辑成为《自复制自动机理论》（Theory of Self-Reproducing Automata）一书出版。

冯·诺依曼设计的自复制自动机是人工生命科学真正的先驱之一，从原则上证明了自我复制的机器的确是可能的，并且提供了自我复制的“逻辑”，后来证明其与生物的自我复制机制惊人的相似。

冯·诺依曼认识到这个结论具有深远的影响。他担心公众对这种自复制机器的反应，不愿看到大众媒介报道“未来这种自复制机器的可能性”。可惜好景不长。1999年，计算机科学家库兹韦尔（Ray Kurzweil）和莫拉韦茨（Hans Moravec）在《灵魂机器的时代》（The Age of Spiritual Machines）和《机器人》（Robot）这两本书中鼓吹了这种具有超级智能并且能自我复制的机器人的可能性，他们认为这种机器人在不远的将来就会被制造出来，他们的书并非虚构，但是相当牵强。2000年，Sun公司的创始人之一乔伊（Bill Joy）在《连线》（Wired）杂志上发表了一篇后来很有名的文章——《为何未来不需要我们》，文中描述了自复制纳米机器的可能性。目前这些预言都还没有应验。不过复杂的自复制机器也许很快就会成为现实：康奈尔大学的机器人专家利普森（Hod Lipson）和他的同事已经制造出了一些简单的自复制机器人。

冯·诺依曼

冯·诺依曼（图8.3）是20世纪科学和数学领域最重要的人物，而且很有趣，在这里值得多说几句。如果你还不知道他的话，应该去了解一下。

不管和谁比，冯·诺依曼都是真正的天才。在相对短暂的一生中，他至少在6个领域作出了基础性的贡献：数学、物理、计算机科学、经济学、生物学和神经科学。人们说起他的故事时，总是忍不住摇摇头，惊叹如此的天才是不是真的是人类能做到的。我很喜欢他的故事，希望在这里与你们分享。

冯·诺依曼出生在匈牙利，小名琼尼。与爱因斯坦和达尔文的大器晚成不同，冯·诺依曼从小就是神童。据说他六岁时就能心算八位数除法。（很久他才发现不是所有人都能做到这一点；他的一本传记中有这样一个故事：“6岁时，有一次他母亲在他面前显得心不在焉，他问妈妈：‘你在算什么？’”）当时他还能和父亲谈论古希腊。

冯·诺依曼18岁进入大学，开始是在布达佩斯，后来又去了德国和瑞士。最初他选择的是化学工程这样的实用课程，但还是无法离开数学。23岁时，因为在数理逻辑和量子力学做出的基础性工作，他获得了数学博士学位。他的工作做得太漂亮了，5年后他就获得了世界上最好的学术职位——加入新成立的普林斯顿高等研究院（IAS），爱因斯坦和哥德尔也是这里的成员。

研究院没有看走眼。此后10年，冯·诺依曼开创了博弈论的研究（写出了被称为“有史以来最好的数理经济学论文”），设计了第一台可编程计算机的原理架构（EDVAC，他为这台计算机写的报告被称为“计算和计算机领域有史以来最重要的文献”），还在第一颗原子弹和氢弹的研制中做出了重要贡献。此后他又致力于研究自复制自动机以及计算机逻辑与大脑运作机制之间的关系。冯·诺依曼在政治上也很活跃（他的立场十分保守，持强烈的反共产主义观点），后来还成为原子能委员会的成员，这个委员会为美国总统在核武器政策方面提供咨询。

除了冯·诺依曼，匈牙利还有一批年龄相仿的科学家后来都成了举世闻名的学者，这被称为“匈牙利现象”。这个群体中包括西拉德，第3章我们已经见过他，物理学家维格纳（Eugene Wigner）、特勒（Edward Teller）和伽柏，数学家厄多斯（Paul Erd s）、科蒙尼（John Kemeny）和拉克斯（Peter Lax）。许多人都奇怪为何当时会聚集这么多耀眼的天才。据冯·诺依曼的传记作者麦克雷（Norman Mac Rae）说：“匈牙利6位诺贝尔奖获得者有5位是生于1875年到1905年间的犹太人，有一次诺贝尔奖得主维格纳被问道，为何在他那一代匈牙利涌现了这么多天才，结果他回答说，他不明白这个问题，匈牙利当时只出现过一位天才，那就是冯·诺依曼。”

冯·诺依曼在许多方面都领先于他的时代。他的目标同图灵类似，想发展信息处理的一般理论，既包括生物也包括技术。他在自复制自动机上的工作就是这项计划的一部分。冯·诺依曼与控制论社团也联系紧密——这是一个由科学家和工程师组成的交叉学科研究群体，致力于研究各种自然界和人工复杂适应系统的共性。现在的“复杂系统”研究的前身就是控制论和系统科学。在最后一章我将进一步探讨它们之间的联系。

冯·诺依曼对计算的兴趣在高等研究院并不是一直都受欢迎。在结束关于EDVAC的工作之后，冯·诺依曼带领几位计算机专家在IAS设计和改进EDVAC的后续机型。这个系统被称为“IAS计算机”；它的设计是后来IBM早期计算机的原型。然而IAS一些纯理论科学家和数学家对此感到不快，认为在这个纯洁的象牙塔中不应进行这种实用性研究，对于冯·诺依曼领导一组气象学家在IAS用这台计算机开展的第一项应用天气预报可能更加反感。一些纯粹主义者认为这类研究不适合研究院。就像IAS的物理学家戴森（Freeman Dyson）说的，“（IAS）数学院分为三个群体，一群是纯数学，一群是理论物理，冯·诺依曼教授单独是一群”。冯·诺依曼去世后，IAS的计算机项目被终止了，IAS的研究人员进行了一场“让研究院没有任何实验科学，没有任何实验室”的运动。戴森称之为“自大狂的报复”。