1701066874
看着图10.7和图10.8，也许你会理解为什么沃尔夫勒姆会对初等元胞自动机这么着迷。这种极为简单的元胞自动机规则究竟是如何产生出如此复杂的图样的呢？
1701066875
1701066876
对沃尔夫勒姆来说，简单的规则涌现出如此的复杂性，这简直就是神迹。他后来说：“规则30自动机是我在科学中所遇到的最让人惊异的事物…… [152] 我花了几年时间来理解它的重要性。最后，我意识到这幅图包含了所有科学长久以来的一个谜团的线索：自然界的复杂性到底从何而来。”沃尔夫勒姆对规则30印象非常深刻， [153] 以至于他用其来构造伪随机数发生器，并申请了专利。
1701066877
1701066878
1701066879
1701066880
1701066881
▲图10.8 规则30的时空图，从随机初始状态开始运行
1701066882
1701066883
沃尔夫勒姆对全部256种初等元胞自动机进行了彻底研究，从各种不同的初始状态开始，观察它们的变化。他让元胞自动机运行较长一段时间，直至元胞自动机的变化稳定下来。他发现最后都进入了4种类型的变化情况：
1701066884
1701066885
类型1：不管初始状态如何，最后几乎都停止在不变的最终图样。规则8就是一个例子，不管初始状态如何，所有元胞很快就都变成了关状态，不再变化。
1701066886
1701066887
类型2：不管初始状态如何，最后要么停止在不变的图样，要么在几个图样之间循环。具体的最终图样依赖于初始状态。
1701066888
1701066889
类型3：大部分初始状态会产生看似随机的行为，虽然也会出现三角形等规则结构。规则30（图10.8）就属于这一类。
1701066890
1701066891
类型4：最有趣的类型。沃尔夫勒姆这样描述：“类型4是有序与随机的混合： [154] 局部结构相当简单，但是这些结构会移动，并以非常复杂的方式相互作用。”规则110（图10.7）就属于这一类。
1701066892
1701066893
沃尔夫勒姆猜想，由于图样和相互作用的复杂性，类型4的所有规则都能进行通用计算。不过很难证明某个具体的元胞自动机、图灵机或其他机器是通用的。图灵证明的只是存在通用图灵机，冯·诺依曼也只是证明自复制自动机同时也是通用计算机。后来有几位科学家证明了简单的元胞自动机（比如生命游戏）是通用的。20世纪90年代，沃尔夫勒姆的一位研究助手库克（Matthew Cook）最终证明了规则110的确是通用的， [155] 这也许是目前已知的最简单的通用计算机。
1701066894
1701066895
复杂 [:1701064782]
1701066896
沃尔夫勒姆的“新科学”
1701066897
1701066898
1998年，库克在圣塔菲研究所的一次会议上做报告，我第一次知道了他的结果。我当时的反应同我的大多数同事差不多，认为“太酷了！太巧妙了！不过没有什么实际或科学意义”。
1701066899
1701066900
和生命游戏一样，规则110也是极为简单的确定性系统产生出无法预测的复杂行为的例子。但在实际中很难设置一个初始状态来产生出所希望的复杂计算。而且规则110会比生命游戏更慢。
1701066901
1701066902
沃尔夫勒姆对这个结果的看法完全不同。在2002年出版的《一种新科学》（A New Kind of Science）中，沃尔夫勒姆将规则110的通用性视为“新的自然定律” [156] ——他提出的计算等价性原理（Principle of Computational Equivalence）——的有力证据。沃尔夫勒姆提出的这个原理包括4部分：
1701066903
1701066904
1.思考自然界中的过程的正确方法是将它们视为计算。
1701066905
1701066906
2.像规则110这样极为简单的规则（或“程序”）都能进行通用计算，这表明通用计算的能力在自然界中广泛存在。
1701066907
1701066908
3.通用计算是自然界中计算的复杂性的上限。也就是说，自然系统或过程不可能产生出“不可计算”的行为。
1701066909
1701066910
4.自然界中各种过程实现的计算在复杂程度上都几乎等价。
1701066911
1701066912
明白了没有？我必须承认，很难解释清楚这个原理的意思，沃尔夫勒姆这本1200页的鸿篇巨著，一个主要目的就是阐释这个原理，并说明它如何适用于各个科学领域。我通读了这本书，但还是没有完全明白沃尔夫勒姆的意思。不过我还是尽力解释一下。
1701066913
1701066914
沃尔夫勒姆说的“自然界中的过程就是计算”指的是类似于图10.7和图10.8中的某种东西。在任意给定时刻，元胞自动机都在通过将其规则应用于其当前状态来处理信息。沃尔夫勒姆认为，自然系统正是以这样的方式运作——它们包含信息，并根据简单规则处理这些信息。在《一种新科学》中，沃尔夫勒姆探讨了量子力学、进化和发育生物学、经济等领域，他想说明这些领域都能描述为使用简单规则进行的计算。本质上，他的“新科学”指的是这样的思想，宇宙和其中的万事万物都能用这种简单的程序来进行解释。这就是大写的计算，非常大。
1701066915
1701066916
因此，根据沃尔夫勒姆的观点，既然规则110这样极度简单的规则都能支持通用计算，那大部分自然系统——基本上应该都比规则110复杂——也就能支持通用计算。而且沃尔夫勒姆相信，给定正确的输入，没有比通用计算机所能进行的计算更复杂的计算。因此这就是自然界中所有可能计算的复杂性的上限。
1701066917
1701066918
第4章曾说过，图灵证明了通用计算机原则上能计算一切“可计算”的东西。但是一些计算要比其他的更简单。虽然都能在同样的计算机上运行，但“计算1+1”的程序肯定没有模拟地球气候的程序复杂，对吧？但沃尔夫勒姆的原理却说，实际进行的所有计算的“复杂程度”本质上都是等价的。
1701066919
1701066920
这到底是什么意思呢？沃尔夫勒姆的理论还没有被广泛接受。这里我将给出我自己的意见。对于前两点，我认为沃尔夫勒姆提出的简单的计算机模型和实验能解释科学中许多过程的观点是正确的，这本书中的例子也证明了这一点。在第12章我还会讲到，我认为可以用信息处理解释许多自然系统的行为。我也发现许多这样的系统似乎的确能支持通用计算，虽然这一点的科学意义目前还不得而知。
1701066921
1701066922
至于第3点，目前也无法知道是否自然界中存在比通用计算机更强大的过程（能计算“不可计算的”东西）。现在已经证明，如果能建造出真正的非数字计算机（能计算具有无穷位小数的数字），你就能用其来解决停机问题 [157] ——我们在第4章看到的图灵不可计算问题。一些人，包括沃尔夫勒姆，不相信自然界真的存在无穷小数——也就是说，他们认为大自然本质上是数字的。两边都没有真正令人信服的证据。
1701066923