宏大的构想，生命作为计算机
http://t.cn/A6WEPJhv
图灵和冯·诺依曼的遗产：生命计算机的架构
Al-Hashimi 返朴 2023-11-16 09:20 发表于北京

加星标，才能不错过每日推送！方法见文末动图

在通用图灵机的基础上，数学家冯·诺依曼进一步发明了自复制机器，回答了生物学中最为深刻的一个问题：为什么所有生物都以DNA形式进行自我描述？图灵和冯·诺依曼，这两位计算机科学先驱偶然发现的生命奥秘并不广为人知，却为研究生物系统勾画出蓝图——把生命系统看作是计算机器。

这篇近期发表于PNAS的文章题为“图灵和冯·诺依曼的遗产：生命计算机的架构”，以DNA聚合酶为例，说明生物分子实际上就是计算机器；并阐释了计算模型的层级结构可以在生物计算领域找到类似结构。通过将生物学简化为计算形式，计算机科学可以用来将生物学系统化。反过来，计算机科学家或许能够挖掘生物计算中的自然宇宙，利用数十亿年的自然演化来发现新的计算模型或算法。展望未来，生物学和计算机科学可以看作是紧密相连的同一门学科，一门研究机器行为的学科。

撰文 | Hashim M. Al-Hashimi
翻译 | 汪显意

审校 | 小木球

编辑 | 梁金

目录

摘要
1. 图灵的通用计算机（Universal Computing Machine）
2. 冯·诺依曼的通用构造机（Universal Constructor）
3. 分子计算（Molecular Computation）
4. 作为计算机的天然生物分子
5. 生物计算（Biological Computation）的一个具体例子
6. 生命计算机的层级
7. 解码生命计算

图片
论文题目：
Turing, von Neumann, and the computational architecture of biological machines
论文地址：
http://t.cn/A6lLi6Lm

图片

摘要

20世纪30年代中期，英国数学家和逻辑学家艾伦·图灵（Alan Turing）发明了一种想象中的机器，它可以模拟人类计算者操纵有限符号装置（finite symbolic configuration）的过程。这一发明为现代可编程计算机提供了基础，从而开创了一个新的科学领域——计算机科学。十年后，在图灵机的基础上，美籍匈牙利数学家约翰·冯·诺依曼（John von Neumann）进一步发明了一种想象中的能够进行开放式演化的自复制机器。通过他的机器，冯·诺依曼回答了生物学中最深刻的问题之一：为什么所有的生物都以DNA形式进行自我描述？两位计算机科学先驱早在DNA双螺旋被发现多年之前，就偶然发现了生命的奥秘，但这个故事并不为人所知，甚至很多生物学家都不知道，你也不会在生物教科书中找到。然而，这个故事在今天和在八十年前一样重要：图灵和冯·诺依曼留下了研究生物系统的蓝图，即把生命系统看作是计算机一样。这种方法可能是回答生物学中许多问题的关键，甚至可能引领计算机科学的再进步。

几个世纪以来，人类文明一直痴迷于建造自动机，令它们通过遵循预定的指令集来执行机械操作。从布谷鸟钟到自动开启的寺庙大门，自动机被用作工具、宗教奇观和解释科学原理的原型。当人们可以用自动机来模仿动物的行为时，便会挑战 “某个东西是‘活的’意味着什么？” 这一说法。大约在20世纪中叶，冯·诺依曼开始对建造真正意义上“活的”自动机展现出兴趣：一个可以自我复制的机器，就可能进化成更复杂的机器。

冯·诺依曼被广泛认为是20世纪最有影响力的思想家之一，他对量子力学的数学基础做出了许多根本性的贡献，是博弈论的先驱之一，也是现代计算机逻辑和设计原理背后的主要架构师[1]。在20世纪40年代早期，冯·诺依曼开始对“控制论”[2]这一新兴领域产生兴趣，该领域关注于研究动物和机器的行为。由于两者都遵循逻辑和机械约束下的指令，控制论学者认为动物和机器在信息、通信和控制机制方面有很多共同之处。

在比较自然和人工机器时，冯·诺依曼发现一个有趣的现象，即生物体可以在几代之后演化成更复杂的生物体[3, 4]。他认为，这种行为很难被设计成一台人工机器。如果机器A要构造机器B，它必须包含完整的B描述。此外，A还必须包含额外的材料来管理B的构造。因此，B不可能比A更复杂，而随着一台机器建造另一台机器，自然的趋势将是退化。

1
图片
图灵的通用计算机（Universal Computing Machine）

艾伦·图灵是20世纪的另一位思想巨人，也是计算机科学和人工智能的先驱，他还因在第二次世界大战期间破解纳粹密码（恩尼格玛）而闻名。为了设计一台可以构建更复杂机器的假想机器，冯·诺依曼从图灵那里获得了灵感，图灵几年前曾构想了一台假想的“通用”机器，可以计算任何其他机器可以计算的任何东西[5]。

图灵发明他的机器不是为了解决任何生物学中的问题，而是为了解决“判定问题（decision problem）”。这个问题被当时杰出的德国数学家大卫·希尔伯特（David Hilbert）称为“数理逻辑的主要问题”，它要求一种通用算法，可以通过有限的过程来决定一个任意的数学命题（陈述）是否可以使用逻辑规则从一组给定的公理中证明。公理是被认为是真的陈述。算法（algorithm）是一个遵循规则来寻找解决方案的系统过程。这个词来源于“algorithmi”，是“Al-Khwarizmi”的拉丁化版本，Al-Khwarizmi 是9世纪的波斯数学家，他首先引入算法来解决代数问题（代数 algebra 一词来源于阿拉伯语“al-jabr”，意思是“破碎部分的重新组合”）。当用特定语言表达时，算法被称为计算机程序。

冯·诺依曼以其数学证明能力而闻名。1926年，在评论希尔伯特的判定问题时，他猜想该问题的判定一定是否定的，但是“我们不知道如何证明这一点”。十年后，图灵证明了这个判定确实是否定性的。理论上的困难在于，人们必须从可以想象到的天文数字级的程序方案中尝试每一个程序，并证明它们都不起作用。图灵想出了一个绝妙的解决方案。将计算简化为简单机器可以执行的基本步骤。通过精确定义什么是可计算的，图灵用他的抽象机器证明了没有一种通用算法可以决定一个公式是否是可证明的。1936年，24岁的图灵发表了一篇具有里程碑意义的论文[5]，这篇论文不仅解决了判定问题，而且可能更重要的是，为计算机科学的新领域和通用可编程计算机奠定了基础。

图灵想象中的机器由一条无限长的磁带和一个磁头组成，磁带被分成几段，磁头可以扫描磁带，一次写一个符号，并沿着磁带向右或向左移动一段。为了“记住”它从一个步骤到下一个步骤所做的事情，图灵允许机器具有不同的“状态”，他设想这些状态代表一个人执行计算时不同的意识状态。然后，机器遵循以转换表形式给出的一组规则，该转换表为每个初始状态和扫描到的符号指定了特定操作（例如，将磁头向左或向右移动一段，或者写入“0”或“1”）及其最终状态。例如，一个规则可能是：“如果磁带磁头处于状态A并扫描0，请将磁头向右移动一段并键入1，然后将其状态更改为状态B”。转换规则还可以指示机器不改变状态或完成并停止操作。依照转换规则，机器根据扫描获得的符号从一个状态跳转到另一个状态，每次执行不同的操作。计算的输入是写在磁带上的原始符号，而输出则是当机器最终停止时写在磁带上的任何东西。

尽管它很简单，但图灵证明了他的机器可以执行一台机器可以执行的任何计算。所需要做的就是向他的机器提供另一台机器的描述，他就可以通过将另一台机器的转换表编码到磁带上来完成。描述机器的转换表本质上就是机器本身，并且可以有无限多个可能的转换表来对应无限多个不同的机器。这种广义计算模型被称为“通用图灵机”（Universal Turing machine），它形成了现代通用可编程计算机的理论基础。

图片
图1. 通用图灵机（Universal Turing machine）

图灵可以用他的抽象机器来枚举所有可能的算法，并证明判定问题没有解决方案[5]。假如这样的算法确实存在，那么就有可能对图灵机进行编程，以预测第二台图灵机是否会在给定任意输入后最终停止运行或陷入恶性的无限循环。图灵证明了这样的图灵机在逻辑上是不可能的。他使用了一种称为归谬法或反证法（reductio ad absurdum）的策略。他假设存在这样一台停下来的机器，然后证明将这台机器喂给自己会导致矛盾。

图灵在证明过程中把机器喂给它自己，在这个过程中引出了自指（self-­reference）概念，这并非巧合。在20世纪初，自指的命题产生了悖论，并在数学领域造成了严重的破坏，对希尔伯特本人热情拥护的正统的公理系统所具有的一致性和完备性提出了质疑。在图灵开始研究他的机器几年前，奥地利逻辑学家和数学家库尔特·哥德尔（Kurt Gödel）给出了关于自指的命题：“这个命题是不可证明的”，表明并非数学系统中的所有正确命题都可以从公理中证明[6]，此举震撼了数理逻辑的核心基础。冯·诺依曼在设计他的自我复制机器时，同样遇到了处于分子生物学核心位置的自指问题。

2
图片
冯·诺依曼的通用构造机（Universal Constructor）

为了建造一台能够演化出更复杂机器的通用自复制机器，冯·诺依曼意识到他需要扩展图灵机的概念，使之可以输出另一台机器，而非打印一串1和0的磁带[1]。冯·诺依曼设想了一台由三个部件组成的机器：一个描述机器的“蓝图（blueprint）”，就像图灵磁带一样，里面有如何建造另一台机器的指令；一个通用的“构造机（constructor）”，用来解码构造机器的指令；还有一种通用的“复制机（copying machine）”，可以复制这些指令[3, 4]。机器使用这些指令复制自己，然后复制这些指令，再将它们输入新机器，以此类推。

为了使这台机器能够制造出超越其自身复杂性的机器，冯·诺依曼还加入了另一个关键因素。40年前，荷兰植物学家雨果·德弗里斯（Hugo de Vries）发现，一种新形态的月见草可以随机自发生长，并繁殖许多代。他为这样的变化创造了一个新词：“突变（mutation）”。正如自然界中的突变可以自发产生一样，冯·诺依曼允许复制机在复制指令时出错。复制错误有可能导致机器产生可执行的变种，那么就可能通过自然选择演化出更复杂的机器。

我们现在知道，生物体就是冯·诺依曼的自我复制机器在真实生命中的一种实现。以DNA序列形式携带指令的遗传磁带首先被转录成相应的信使RNA磁带，然后输入到一个通用的构造机——“核糖体”中，核糖体将RNA信息翻译成相应的氨基酸序列，这些氨基酸序列指定了蛋白质磁带。反过来，蛋白质磁带会自发地折叠成分子装置，为细胞提供主要的功能。当生物体繁殖时，DNA磁带被聚合酶复制并从父母传给后代，这就解释了遗传是如何工作的。复制DNA时可能会发生错误，导致生物种群多样化。最终，一些突变会展现出一种优势，经过几代的演化，那些具有优势的生物体会迅速繁殖并占据整个种群。这种突变和自然选择的循环就是生物学家所说的“达尔文进化论（Darwinian evolution）”——这个过程标志着生物学和生命的开始。从DNA到RNA，再到蛋白质的信息流，就是弗朗西斯·克里克（Francis Crick）所说的“分子生物学的中心法则（Central Dogma of Molecular Biology）”[7]。

1948年9月20日，在加州理工学院举行的“大脑行为机制的希克森研讨会”上，冯·诺依曼在一次演讲中描述了他的自复制机器[1, 3]（图2）。这是在DNA双螺旋结构被发现的5年前[8]，在克里克提出分子生物学的中心法则的12年前[7]。那时，DNA还是遗传信息载体的主要竞争者。

图片
图2.（左）1948年宣传希克森研讨会的传单。（右）与会者合影。后排从左到右分别是 Henry W. Brosin，Jeffress，Paul Weiss，Donald B Lindsley，John von Neumann，J. M. Nielsen，R. W. Gerard，H. S. Liddell。前排分别是Ward C Halstead，K. S. Lashley，Heinrich Klüver，Wolfgang Köhler 和 R. Lorente de No。图片由加州理工学院档案管理员Loma Karklins提供。

包括冯·诺依曼的演讲在内的研讨会内容于1951年被集合成书[3]。根据演讲稿，冯·诺依曼清楚地看到了他的自复制机器和生物体之间的联系，他指出，“……指令ID大致影响基因的功能。同样清楚的是，复制机B执行繁殖的基本行为，即遗传物质的复制，这显然是活细胞增殖的基本操作。也很容易看出，系统E，特别是ID的任意改变，如何能表现出某些典型的性状，这些性状与突变有关，通常是致命的，但有也有可能继续繁殖。”

冯·诺依曼认为，为了实现自我复制，人们需要一种机制，不是复制机器本身，而是复制一套建造机器的指令，在这一点上，冯·诺依曼的非凡洞察力是公认的。他的逻辑依据是，机器是“变化和反应”（varying and reactive）的，仅仅观察它就可能导致难以预见的变化。相反，指令带是“准静态的”，并且不太可能随着观察而改变。因此，由于生物体需要复制，它们会携带构建自身的指令，而指导如何构建生物体的指令会比生物体自身的指令更精确地被复制。