宇宙是个计算机吗？｜Wolfram与他的「计算等价性原理」

每年，WolframResearch公司都要举办一次暑期学校（WolframSummerSchool）[1]，交流在所谓「新科学」（NewKindofScience）领域的进展与观点。这个活动至今已经举办了13年，而每一年都会涉及的一个内容，就是「复杂」本身——什么是复杂？复杂有有没有极限？

StephenWolfram照片

为了回答这个问题，Wolfram在2002年专门出版了一本一千余页的煌煌巨著来阐述他的研究——《ANewKindofScience》（中文：一种新科学）。而这本书的「高潮」之处，则在于最后一章的「计算等价性原理」（ThePrincipleofComputationalEquivalence）。

扎克伯格桌上的《ANewKindofScience》

计算等价性原理（ThePrincipleofComputationalEquivalence）简单来说，就是认为任何看起来比较复杂的系统（流体、社会系统、蚁群，等等），他们的复杂度都是相同的，而且都达到了复杂性的极限——它们的复杂度，与宇宙中其他极为复杂的系统，例如大脑，是相同的。而进一步的，这个原理似乎从计算的视角，回答了「人能否理解宇宙」，这样的「终极问题」。

而要理解这个宏大的原理、理解这个关于「复杂性」的原理，则需要从一个最简单的系统出发——元胞自动机。

元胞自动机CellularAutomata

二十世纪四十年代，冯·诺依曼在研究自复制机[2]的时候，提出了「元胞自动机」的概念。元胞自动机是一个根据特定规则演化的离散系统。Wolfram则考虑了一个最简单的元胞自动机，如下图所示，我们称之为「基础元胞自动机」（ElementaryCellularAutomata，ECA）。

图2：30号基础元胞自动机。

基础元胞自动机，是一个在一维空间上，离散演化的系统，横轴是空间，纵轴是时间。在给定一个初始状态（第一行）之后，系统按照最下面的规则演化——按照规则的第六条：（黑色为1，白色为0），可以知道，第一行的黑色方块，在下一步的演化之中，也是黑色。上图完全由这八个简单的规则演化而来。这里所谓「30号」，也是从规则得到的，将八个规则按顺序排列，得到01字串，将之视为一个二进制数00011110，那么很容易算得，。0~255，每一个数字对应一个规则，后面我们会一直使用这种表示方法。

如果我们延长演化的步数，比如128步，可以发现，其行为变得极为复杂：

图3：演化128步后的时空图

我们可以尝试其他很多规则，会发现其行为非常丰富：

图4：六种不同的基础元胞自动机，他们行为迥异，混乱、秩序，分形，展现出了非常丰富的行为。

这里展现的系统，都基于极为简单规则，而却能产生出非常丰富的行为。有的系统，甚至可以作为随机数生成器来使用[3]。上面的这些事实，给我们的第一个启发就是，「复杂」可以从极为简单的规则中涌现出来。那么，就可以定性解释「为何自然界中，复杂行为如此常见」——只要任何规则、动力学机制，都包含了这些简单规则，那么它就有潜力产生复杂的行为。而由于上面规则之简单，使得很多规则更复杂的系统，都很容易将之包含进去。

然而，这样给人们带来了一个问题：如何度量复杂性？复杂性的极限在哪里？

要回答这个问题，一个最自然的出发点，就是去寻找复杂性相同的系统。所谓「A与B复杂性相同」，从计算的角度看，就是认为「A可以模拟B」，而「B也可以模拟A」。我们从这个问题内的一部分开始：A系统模拟B系统。

无处不在的等价

在Wolfram的书中，他列举了大量这样的关系：元胞自动机可以等价于各种其他系统的行为。从数字电路，到数论，再到逻辑代数，而后一路推进，到通用图灵机——可以模拟一切可计算系统的系统。

一个最简单的例子，就是规则132：

规则132的演化图

规则132的规则图

这个系统完成了如下的计算：

如果n是偶数，则返回0；如果n是奇数，则返回1

其中n就是第一行黑色方块的数量。经过至多次演化之后，得到f(n)。

对于代数运算，元胞自动机显然可以做的更多。

它可以计算n的平方：

下面的元胞自动机规则比上面要稍微复杂一些。

这个元胞自动机可以计算n的平方

同样，给定初始第一行黑色方块的数量n，系统演化到稳定之后，其黑色方块的数量就是.也就是说，它等价于：

元胞自动机甚至可以用来寻找素数：

每一条白线就对应一个素数

其中左边的每一条白线，都对应着一个素数。也就是说，这个元胞自动机，等价于运算：

既然我们要讨论「无处不在的等价」，那么仅仅代数、数论运算，是远远不够的。

基本的逻辑运算：

使用简单规则的元胞自动机，可以支持与、或，以及由其构造出的各种运算：

基本的逻辑运算

可以看到，下面的规则列表比之前长了很多。同时，基础元胞自动机中的146，190号规则，可以进行逻辑运算：

上面的这些元胞自动机，是沟通简单与复杂的桥梁之一——通过代数、数论，以及逻辑运算，可以构造出复杂度远远超过规则的行为。

从等价到普适

从上面的例子，人们很自然的会想到，是否存在一个系统，规则极为简单，而却能模拟其它任何系统[4]呢？

一个最初的想法，就是用更复杂的元胞自动机，去模拟所有基础元胞自动机。事实表明，这是可以的，但其规则极为复杂，这里不详述其规则，只大致介绍一下：

通过设定初值，即第一行元胞颜色的顺序，它可以模拟所有基础元胞自动机，如上图，分别是254号、90号和30号。

然而，这样「工匠」一般的搜寻，对于理论来说，并没有太多的助益——无非是找到了很多等价的系统而已。然而，后来的一个突破性进展，直接导致了「计算等价性原理」的诞生。

在2000年，Wolfram的一个助手，MatthewCook，证明了基础元胞自动机中的规则110是图灵完备的[5]。

110号元胞自动机的演化图，它等价于通用计算机

110号元胞自动机的规则图

就是上图的这种元胞自动机。同样的，使用八个参数确定出的简单规则。

为了说明这个研究的意义，需要先简单说一下「通用图灵机」（UTM）是什么，「图灵完备」是什么。一个直观的想象就是，通用图灵机（UTM）是一个抽象的电脑。是只用来描述电脑计算能力的一个抽象模型。从另一个角度来说，电脑上能进行的计算，图灵机都能进行。图灵机是目前可实现的计算系统中，计算能力最强的系统（包括量子计算机，也是图灵机）。而所谓「图灵完备」，简单的说，就是一个系统，等价于通用图灵机。

那么，既然110号规则已经是图灵完备的了，它便可以运行任何程序——从最简单的，到最复杂的。而既然它可以运行最为复杂的程序，那么这个系统本身，是不是可以认为，已经达到了复杂性的极限了呢？Wolfram给出的回答是：「是的，UTM就是复杂性的极限，而且很容易达到」。

另一个需要注意的，就是110号规则本身非常简单——这意味着，其他规则稍稍复杂一些的系统，其规则本身，很有可能已经包含了110号元胞自动机。这暗示着，有大量的系统是通用图灵机，他们的复杂度相同，都是计算复杂性的极限。

那么问题就来了，一个系统很容易包含其他系统的行为吗？最近的一个研究[6]发现，当我们逐渐增大观察系统的标尺时（实空间重整化），会有越来越多的系统能够互相模拟，或者单向的模拟。

普通的元胞自动机，以单个元胞为单元，即0或1.但如果我们引入重整化的思想，将两个，或者三个元胞作为一个单元，比如我们定义：

这时，初值只有{1,1}和{0,0}的排列，而不会出现{,0,1,0,}这样的情况。我们称这个过程为「编译」，而这个变换的规则就是「编译器」（compiler）。这时我们发现，94号元胞自动机，可以展现出90号元胞自动机的行为：

这意味着，94号规则，包含了90号规则的行为。这里我们是将两个元胞合成一个单元，如果是「三变一」、「四变一」呢？研究发现，当这个数字增长的时候，能够互相模拟的系统越来越多：

上图中，横轴是编译器的尺寸，而纵轴则是能够互相模拟的系统的数量——即出现的频率。不同颜色线，代表了不同的元胞自动机族。这张图表明，随着编译器尺寸的增加，系统之间，一方能模拟另一方的概率趋近于1，或者一个很接近1的值。

这个结果非常重要！这暗示了，在自然界之中，系统间的模拟，也是非常常见的。

这样再回到前面的一段话：

另一个需要注意的，就是110号规则本身非常简单——这意味着，其他规则稍稍复杂一些的系统，其规则本身，很有可能已经包含了110号元胞自动机。这暗示着，有大量的系统是通用图灵机，他们的复杂度相同，都是计算复杂性的极限。

现在只要再有一个假设，就可以得到计算等价性原理了：

「宇宙就是一个计算机」

很多人可能觉得这一句话很多余，因为似乎只是一个看世界的不同视角罢了。但是需要注意的是，这个假设，暗含了一个很强的要求：宇宙中所有的行为、现象、数值，都是可计算的，是可以在图灵机上，通过运行程序而得到的。

举个例子说明这个假设的必要性：

2015年，一项研究表明，二维无限大晶格材料的能隙是不可计算的[7]。

然而，在我们目前的认知之中，宇宙间不存在无限大的物体，而那项研究也证明了，任何有限大的二维晶格，其能隙都是可计算的——目前为止，还没有真实的物理体系被证明是不可计算的。

有了「宇宙就是一个计算机」这个假设之后，我们便可以提出「计算等价性原理」了。Wolfram的表述是：

几乎所有看起来不那么简单过程，他们的复杂度都是相同的。（Almostallprocessesthatarenotobviouslysimplecanbeviewedascomputationsofequivalentsophistication.）

而且，「复杂度的极限是很容易达到的」，只要规则稍稍丰富一点点，系统就会展现出宇宙间最复杂的行为——通用图灵机的各种行为。这意味着，之所以我们能够在宇宙中看到如此多、如此丰富的复杂行为，其根本原因是，他们的动力学机制，支持图灵完备的运算——从而包含了从最简单，到最复杂的所有行为。

基于计算等价性原理的另一个推论就是「人可以理解宇宙」，或者是，渐进地理解宇宙。如果我们从计算的视角来定义「理解」，我们就能得到这个推论：我们定义A「理解」B，是A能够在大脑，或者自身的某个系统之中，具象，或者抽象的重现出B。即A能模拟B、A能运行B。

我们说「我理解一个物理定律」，最基本的，就是能够在大脑中通过物理图像、公式，来描述某个规则。

如果计算等价性原理是错的，那么相对简单的大脑如何理解相对复杂的宇宙呢？而如果承认计算等价性原理，我们就可以说，大脑的复杂性是与宇宙相同的，唯一的限制是容量，但我们依旧可以用计算机来拓展它的理解力。

Wolfram曾在果壳的专访[8]中说：「宇宙的本质是计算」。恐怕其深意也在于此。

参考文献

1:WolframSummerSchool；

2:Neumann,(1966).TheoryofSelf-ReproducingAutomata.(,Ed.).Champaign,IL,USA:UniversityofIllinoisPress.

3:Tomassini,M.,Sipper,M.,Perrenoud,M.(2000).Onthegenerat,49(10),1146–1151.

4:指可计算的系统；

5:Cook,M.(2004).,15(1),1–40.

6:JürgenRiedel,HectorZenil.().Cross-boundaryBehaviouralReprogrammabilityofCellularAutomatafromEmulationNetworks.

7:[1502.04573]UndecidabilityoftheSpectralGap(fullversion)，科普版见：不可解的物理学难题，源于数学核心的悖论

8:斯蒂芬·沃尔夫勒姆：宇宙的本质是计算

很赞哦!（112）