第10章 元胞自动机、生命和宇宙

自然界中的计算

《科学》杂志不久前出版了一篇文章，题为《社会性昆虫行为的计算》（Getting the Behavior of Social Insects to Compute），文中介绍了一些昆虫学家的工作，他们将蚂蚁群体的行为等同于“计算机算法”，每只蚂蚁都执行简单的程序，使得整个种群作为一个整体执行复杂的计算，比如在决定何时将巢穴搬往何地的问题上形成一致。

如果由一只蚂蚁来领导和决策，很容易就能在计算机上编出程序来进行计算。其他蚂蚁只需按照领导者的决策来做就行了。然而，在前面我们已经看到，在蚂蚁群体中没有领导者；蚁群“计算机”由数百万只自主的蚂蚁组成，每只蚂蚁都只是根据与一小部分蚂蚁的交互来进行决策和行动。这种计算与具有CPU和内存的普通电脑进行的计算差别很大。

与此类似，1994年三位杰出的大脑科学家也写了一篇文章：“大脑是计算机吗？”他们认为：“如果我们同意接受更宽泛的计算概念，答案就一定是‘是’。”同蚁群一样，大脑的计算方式——数以亿计的神经元并行工作，而无须中央控制——也与现代的数字计算机的运作方式完全不同。

在前两章我们探讨了计算机中的生命和进化。在这一部分，我们来看看相对的思想，以及计算在自然界中的广泛存在。自然系统的“计算”指的是什么呢？大致上说，计算是复杂系统为了成功适应环境而对信息的处理。但是这样的说法还能更精确些吗？信息在哪里？复杂系统又是如何处理信息的？

为了让这类问题更易于研究，科学家们通常会将问题理想化——也就是尽可能简化，但仍然保留问题的主要特征。鉴于此，许多人都用元胞自动机这种理想化的复杂系统模型来研究自然界中的计算。

元胞自动机

在第4章曾讲过，图灵机将“明确程序”——也就是计算——的概念进行了形式化。计算就是图灵机根据机器的规则集将带子上的初始输入转换成停机时带子上的输出。这个抽象的机器就是后来所有数字计算机的设计原型。由于冯·诺依曼对计算机设计作出的贡献，现在的计算机架构被称为“冯·诺依曼体系结构”。

冯·诺依曼体系结构包括存储数据和程序指令的随机存取存储器（RAM）、从存储器存取指令和数据并执行指令处理数据的中央处理单元（CPU）。你可能知道，虽然程序员们编程时使用的是高级语言，存储在计算机中的指令和数据却是0/1组成的串。执行指令就是将这种0/1码译成基本的逻辑操作让CPU执行。只需要几种基本的逻辑操作就能实现所有计算，现代CPU每秒能执行数亿次这样的逻辑操作。

元胞自动机是理想化的复杂系统，结构完全不同于计算机。想象一块板子上排列着许多灯泡（图10.1），每个灯泡与四周以及斜对角的灯泡连在一起。在图中只画了其中一个灯泡的连接线，不过姑且想象所有灯泡都有连接线。

图10.2中（左边的盒子），有些灯泡已经点亮（为了简洁，我没有画灯泡的连线）。先设定好灯泡的开关状态，然后各个灯泡开始不断定时“更新状态”——选择开或关，所有灯泡都同步变化。你可以将这个灯泡阵看作萤火虫发光的模型，每只萤火虫都根据周围萤火虫的闪灭来调整自己是亮还是灭；也可以看作神经元的激发模型，各个神经元受周围神经元的状态激发或抑制；或者就当作抽象艺术也行，如果你愿意的话。

灯泡每一步如何“决定”是开还是关呢？它们都遵循一些规则，根据邻域内灯泡的状态——也就是相邻的8个灯泡和它自己的状态——来决定下一步的状态（是开还是关）。

例如，规则可以是这样：“如果邻域内的灯泡（包括自己）点亮的超过一半，就点亮（如果本来就是亮的，则不变），否则就熄灭（如果本来就是灭的，则不变）。”也就是说，邻域中9个灯泡，如果有5个或5个以上是亮的，中间的灯泡下一步就是亮的。我们来看看灯泡阵列下一步会怎么变。

图10.1的文字中说了，为了让每个灯泡都有8个邻居，阵列的四边是回绕相连的。可以想象成上边和下边合到一起，左边和右边合到一起，形成一个面包圈形状。这样每个灯泡就都有8个邻居。

现在再来看上面给出的规则。图10.2是初始设置和变化一次后的状态。

也可以使用更复杂的规则，例如，“如果邻域中点亮的灯泡不少于2个，不多于7个，就点亮，否则就熄灭”，这样阵列的变化就会不一样。或者这样，“如果刚好1个灯泡是灭的，或者4个是亮的，就点亮，否则就熄灭”。可能的规则很多。

到底有多少种可能的规则呢？说“很多”还太保守了。答案是“2的512次幂”（2512）注5，这个数字很大，比宇宙中的原子数量还大许多倍。（注释中有答案的推导过程。）

注5 “答案是‘2的512次幂’（2512）”：这一章后面会讲到，要定义一条规则，你必须说明，对于邻域内灯泡的所有可能状态组合，中心位置的灯泡下一步的状态是什么。邻域包括周围8个灯泡和中间的灯泡本身，每个灯泡的状态都可以是开或关，因此可能的状态组合的数量为29=512。而对每种状态组合，都可以用“开”或“关”作为中间灯泡下一步的状态，因此对全部512种组合可能给出的规则配置数量就为2512≈1.3×10154。

这个灯泡阵列其实就是一个元胞自动机。元胞自动机是由元胞组成的网格，每个元胞都根据邻域的状态来选择开或关。（广义上，元胞的状态可以随便定多少种，但是这里我们只讨论开/关状态。）所有的元胞遵循同样的规则，也称为元胞的更新规则，规则根据各元胞邻域的当前状态决定元胞的下一步状态。

为什么说这么简单的系统会是复杂系统的理想化模型呢？同自然界的复杂系统一样，元胞自动机也是由大量简单个体（元胞）组成，不存在中央控制，每个个体都只与少量其他个体交互。而且元胞自动机也能表现出非常复杂的行为，它们的行为很难甚至不可能通过其更新规则来预测。

同其他许多精彩的思想一样，元胞自动机也是由冯·诺依曼发明的，他在20世纪40年代受他的一位同事——数学家乌拉姆——的启发提出了这个思想。（为了与冯·诺依曼体系结构相区别，元胞自动机经常被称为非冯·诺依曼体系结构，这是计算机科学的一大笑话。）第8章说过，冯·诺依曼想要将自我复制机器的逻辑形式化，而他用来研究这个问题的工具就是元胞自动机。简单地说，他设计了一种元胞自动机规则，能完美复制任意元胞自动机的初始形态，他的规则中元胞不止两种状态，而是29种。

冯·诺依曼还证明他的元胞自动机等价于通用图灵机（参见第4章）。元胞的更新规则扮演了图灵机读写头的规则的角色，而元胞阵列的状态则相当于图灵机的带子——也就是说，它可以编码通用图灵机运行的程序和数据。元胞一步一步地更新相当于通用图灵机一步一步地迭代。能力等价于通用图灵机的系统（也就是说，通用图灵机能做的，它也能做）被称为通用计算机，或者说能进行通用计算。

生命游戏

冯·诺依曼的元胞自动机规则相当复杂。1970年，数学家康威（John Conway）发现了一种简单得多的两状态通用图灵机，也能进行通用计算。他称之为“生命游戏”。我不知道为什么叫作“游戏”，只知道“生命”来自于康威对其规则的解释。将状态为开的元胞看作活的，状态为关的元胞看作死的。康威用四种生命过程来定义规则：出生，死元胞的相邻元胞中如果刚好有3个是活的，下一步就变成活的；存活，活元胞的相邻元胞有2—3个是活的，下一步就能继续存活；过于稀疏，活元胞的相邻活元胞如果少于2个就会死去；过度拥挤，活元胞的相邻活元胞如果多于3个就会死去。

康威当时是想寻找一个能产生类似生命的元胞自动机。出人意料的是，生命游戏的行为丰富而有趣，以至于现在出现了一个爱好者团体，他们的主要兴趣就是发现能产生有趣行为的初始设置。

图10.3就是其中一个有趣的行为，被称为滑翔机。这里我们不再用灯泡，就用黑格子表示开（活），用白格子表示关（死）。图10.3中可以看到有一个滑翔机向东南方向移动。当然，元胞并没有动，它们都是固定的。移动的是由活状态元胞形成的一个不消散的形状。因为元胞自动机的边界是回绕相连的，所以滑翔机能一直移动。

爱好者们还发现了其他复杂的形状，例如太空船，它类似于滑翔机，而且更有趣；滑翔机发射器，它会不断射出新的滑翔机。康威证明，通过用变化的开/关状态模拟读写头在带子上的读写，就能让生命游戏模拟图灵机。

康威还给出了生命游戏模拟通用计算机的证明框架（后来由其他人细化）。将程序和输入数据编码为开关状态初始设置，生命游戏运行后产生的图样表示程序的输出。

康威在证明中组合使用滑翔机发射器、滑翔机等结构来实现与、或、非等逻辑运算。人们早已发现，能用各种可能来组合这些逻辑操作的机器就能进行通用计算。康威的证明表明，原则上，逻辑运算的所有可能组合都能在生命游戏中实现。

像生命游戏这么简单的元胞自动机在原则上能运行标准计算机运行的程序，这真是让人吃惊。不过，实际上，稍微复杂一点的计算就需要大量逻辑运算，并以各种方式相互作用，因此要设计出能实现复杂计算的初始设置基本不太可能。即使设计得出来，计算也会慢得让人无法忍受，更不要说用这种并行的非冯·诺依曼结构的元胞自动机来模拟传统冯·诺依曼结构计算机需要耗费的大量资源。

因此没有人用生命游戏（或其他“通用”元胞自动机）来进行真实计算或是模拟自然系统。我们只是想利用元胞自动机的并行特征以及它产生复杂图形的能力。下面先来看看元胞自动机能够产生的图形种类。

四类元胞机

20世纪80年代初，普林斯顿高等研究院的物理学家沃尔夫勒姆对元胞机着了迷。沃尔夫勒姆（图10.4）是传奇般的天才人物。他1959年生于伦敦，15岁就发表了他的第一篇物理学论文。两年后，在牛津大学一年级的暑假，大部分人这时候都会去打工挣钱，或是背着背包搭顺风车周游欧洲，沃尔夫勒姆却写了一篇关于“量子色动力学”的论文，这篇论文被诺贝尔奖获得者物理学家盖尔曼注意到，他邀请沃尔夫勒姆加入他在加州理工的研究小组。两年后，沃尔夫勒姆获得了理论物理博士学位，而这时他才20岁（大部分人大学毕业后至少需要5年才能获得博士学位）。他留在加州理工任教，此后不久又获得了第一届麦克阿瑟天才奖。两年后，他受邀加入普林斯顿高等研究院。真是让人叹为观止。他有了名气，又有资金支持，可以想干什么就干什么，他决定研究元胞自动机动力学。

根据理论物理学的惯例，沃尔夫勒姆从元胞自动机最简单的形式来研究其行为，他用的是一维两状态的元胞自动机，每个元胞仅与两个相邻元胞相连[图10.5（a）]。沃尔夫勒姆称之为“初等元胞自动机（elementary cellular automata）”。他认为，如果这种看上去极为简单的系统也理解不了，就更不可能理解更复杂的（例如，两维或多状态的）元胞自动机。

图10.5描绘了一个初等元胞自动机的规则。图10.5（a）是元胞格子——一排元胞，每个都与两侧相邻的元胞相连。这里仍然是用方格表示元胞——黑表示开，白表示关。两头的格子回绕连在一起，形成一个环。图10.5（b）是元胞遵循的规则：3个相邻元胞总共有8种可能状态组合，对于每种状态组合都给出了中间元胞的更新状态。例如，当3个元胞都是关状态时，中间元胞下一步就是关状态。同样，当3个元胞的状态为关—关—开时，中间元胞下一步就会变成开状态。这里规则指的是整个状态组合和更新状态的表，而不仅仅是表中的一行。图10.5（c）展示了这个元胞自动机的时空图。最顶上一行是一维元胞机的初始状态设置。下面跟着的依次是每一步更新后的状态。这种图被称为时空图，因为它表现了元胞自动机的立体构型随时间的变化。

3个元胞有8种可能的状态组合[图10.5（b）]，而每种可能的状态组合又有两种可能的元胞更新状态，因此初等元胞自动机总共有256（28）种可能的规则。20世纪80年代时，计算机的性能已经足以让沃尔夫勒姆对这些规则逐个进行研究，设定各种初始状态，然后观察它们的变化。

沃尔夫勒姆给初等元胞自动机的规则都编了号，编号方法见图10.6。他将开状态记为“1”，关状态记为“0”，根据更新状态将规则记为0/1串，最前面一位对应3个元胞都为开时的更新状态，最后一位则对应3个元胞都为关时的更新状态。这样图10.5中的规则就记为0 1 1 0 1 1 1 0。然后沃尔夫勒姆将这个0/1串当作二进制数。0 1 1 0 1 1 1 0作为二进制数等于十进制数110。因此这个规则就叫作“规则110”。如果更新状态是0 0 0 1 1 1 1 0，则为“规则30”。（注释中介绍了如何将二进制数转换为十进制数。注6）

注6 “注释中介绍了如何将二进制数转换为十进制数”:十进制（基为10）数的每一位对应一个10的幂，例如:235=2×102+3×101+5×100（其中100=1）。基为2时，每一位对应的则是2的幂。例如235表示成基为2的数就是11101011:11101011=1×27+1×26+1×25+0×24+1×23+0×22+1×21+1×20=235

沃尔夫勒姆和他的同事开发了一种专门的计算机语言——Mathematica——用来简化元胞自动机的模拟。沃尔夫勒姆用Mathematica编程运行元胞自动机，并绘制它们的时空图。例如，图10.7和图10.8与图10.5类似，只是规模大些。图10.7中有200个元胞，初始状态随机设置，应用的更新规则是110，逐行往下更新了200时间步。图10.8应用的则是规则30，也是从随机初始状态开始。

看着图10.7和图10.8，也许你会理解为什么沃尔夫勒姆会对初等元胞自动机这么着迷。这种极为简单的元胞自动机规则究竟是如何产生出如此复杂的图样的呢？

对沃尔夫勒姆来说，简单的规则涌现出如此的复杂性，这简直就是神迹。他后来说：“规则30自动机是我在科学中所遇到的最让人惊异的事物……我花了几年时间来理解它的重要性。最后，我意识到这幅图包含了所有科学长久以来的一个谜团的线索：自然界的复杂性到底从何而来。”沃尔夫勒姆对规则30印象非常深刻，以至于他用其来构造伪随机数发生器，并申请了专利。

沃尔夫勒姆对全部256种初等元胞自动机进行了彻底研究，从各种不同的初始状态开始，观察它们的变化。他让元胞自动机运行较长一段时间，直至元胞自动机的变化稳定下来。他发现最后都进入了4种类型的变化情况：

类型1：不管初始状态如何，最后几乎都停止在不变的最终图样。规则8就是一个例子，不管初始状态如何，所有元胞很快就都变成了关状态，不再变化。

类型2：不管初始状态如何，最后要么停止在不变的图样，要么在几个图样之间循环。具体的最终图样依赖于初始状态。

类型3：大部分初始状态会产生看似随机的行为，虽然也会出现三角形等规则结构。规则30（图10.8）就属于这一类。

类型4：最有趣的类型。沃尔夫勒姆这样描述：“类型4是有序与随机的混合：局部结构相当简单，但是这些结构会移动，并以非常复杂的方式相互作用。”规则110（图10.7）就属于这一类。

沃尔夫勒姆猜想，由于图样和相互作用的复杂性，类型4的所有规则都能进行通用计算。不过很难证明某个具体的元胞自动机、图灵机或其他机器是通用的。图灵证明的只是存在通用图灵机，冯·诺依曼也只是证明自复制自动机同时也是通用计算机。后来有几位科学家证明了简单的元胞自动机（比如生命游戏）是通用的。20世纪90年代，沃尔夫勒姆的一位研究助手库克（Matthew Cook）最终证明了规则110的确是通用的，这也许是目前已知的最简单的通用计算机。

沃尔夫勒姆的“新科学”

1998年，库克在圣塔菲研究所的一次会议上做报告，我第一次知道了他的结果。我当时的反应同我的大多数同事差不多，认为“太酷了！太巧妙了！不过没有什么实际或科学意义”。

和生命游戏一样，规则110也是极为简单的确定性系统产生出无法预测的复杂行为的例子。但在实际中很难设置一个初始状态来产生出所希望的复杂计算。而且规则110会比生命游戏更慢。

沃尔夫勒姆对这个结果的看法完全不同。在2002年出版的《一种新科学》（A New Kind of Science）中，沃尔夫勒姆将规则110的通用性视为“新的自然定律”——他提出的计算等价性原理（Principle of Computational Equivalence）——的有力证据。沃尔夫勒姆提出的这个原理包括4部分：

1．思考自然界中的过程的正确方法是将它们视为计算。

2．像规则110这样极为简单的规则（或“程序”）都能进行通用计算，这表明通用计算的能力在自然界中广泛存在。

3．通用计算是自然界中计算的复杂性的上限。也就是说，自然系统或过程不可能产生出“不可计算”的行为。

4．自然界中各种过程实现的计算在复杂程度上都几乎等价。

明白了没有？我必须承认，很难解释清楚这个原理的意思，沃尔夫勒姆这本1200页的鸿篇巨著，一个主要目的就是阐释这个原理，并说明它如何适用于各个科学领域。我通读了这本书，但还是没有完全明白沃尔夫勒姆的意思。不过我还是尽力解释一下。

沃尔夫勒姆说的“自然界中的过程就是计算”指的是类似于图10.7和图10.8中的某种东西。在任意给定时刻，元胞自动机都在通过将其规则应用于其当前状态来处理信息。沃尔夫勒姆认为，自然系统正是以这样的方式运作——它们包含信息，并根据简单规则处理这些信息。在《一种新科学》中，沃尔夫勒姆探讨了量子力学、进化和发育生物学、经济等领域，他想说明这些领域都能描述为使用简单规则进行的计算。本质上，他的“新科学”指的是这样的思想，宇宙和其中的万事万物都能用这种简单的程序来进行解释。这就是大写的计算，非常大。

因此，根据沃尔夫勒姆的观点，既然规则110这样极度简单的规则都能支持通用计算，那大部分自然系统——基本上应该都比规则110复杂——也就能支持通用计算。而且沃尔夫勒姆相信，给定正确的输入，没有比通用计算机所能进行的计算更复杂的计算。因此这就是自然界中所有可能计算的复杂性的上限。

第4章曾说过，图灵证明了通用计算机原则上能计算一切“可计算”的东西。但是一些计算要比其他的更简单。虽然都能在同样的计算机上运行，但“计算1+1”的程序肯定没有模拟地球气候的程序复杂，对吧？但沃尔夫勒姆的原理却说，实际进行的所有计算的“复杂程度”本质上都是等价的。

这到底是什么意思呢？沃尔夫勒姆的理论还没有被广泛接受。这里我将给出我自己的意见。对于前两点，我认为沃尔夫勒姆提出的简单的计算机模型和实验能解释科学中许多过程的观点是正确的，这本书中的例子也证明了这一点。在第12章我还会讲到，我认为可以用信息处理解释许多自然系统的行为。我也发现许多这样的系统似乎的确能支持通用计算，虽然这一点的科学意义目前还不得而知。

至于第3点，目前也无法知道是否自然界中存在比通用计算机更强大的过程（能计算“不可计算的”东西）。现在已经证明，如果能建造出真正的非数字计算机（能计算具有无穷位小数的数字），你就能用其来解决停机问题——我们在第4章看到的图灵不可计算问题。一些人，包括沃尔夫勒姆，不相信自然界真的存在无穷小数——也就是说，他们认为大自然本质上是数字的。两边都没有真正令人信服的证据。

第4点对我来说没有意义。我认为很有可能我的大脑支持通用计算（至少在我有限的记忆容量允许的范围内），而线虫的脑也（基本上）是通用的，但我不认为我们进行的计算在复杂程度上是等价的。

沃尔夫勒姆走得更远，他认为存在一个简单的类似元胞自动机的规则可以作为“宇宙的终极确定性模型”，这个原初元胞自动机的计算是存在的万事万物的源头。这个规则有多长呢？沃尔夫勒姆说：“我猜其实相当短。”但是到底多长呢？他说：“我不知道。也许三四行Mathematica程序。”小写的计算。

《新科学》在2002年出版后引起了轰动——很快就位居亚马逊网站的畅销书榜首，并在之后很久都留在畅销书榜中。沃尔夫勒姆为了这本书的出版成立了沃尔夫勒姆媒体公司（Wolfram Media），在书出版后这家公司进行了大规模的宣传活动。对这本书的看法分成两个极端：一些读者认为这本书棒极了，是革命性的；另一些人认为这本书盲目自大，缺乏实质和原创性[例如，批评者指出物理学家祖斯（Konrad Zuse）和弗瑞德金（Edward Fredkin）早在20世纪60年代就提出了宇宙是元胞自动机的理论]。不管怎样，我们这些元胞自动机的爱好者都认为，《新科学》至少很好地宣传了元胞自动机。