1701066861
1701066862
1701066863
1701066864
1701066865
▲图10.6 沃尔夫勒姆使用的初等元胞自动机命名系统
1701066866
1701066867
沃尔夫勒姆和他的同事开发了一种专门的计算机语言——Mathematica——用来简化元胞自动机的模拟。沃尔夫勒姆用Mathematica编程运行元胞自动机，并绘制它们的时空图。例如，图10.7和图10.8与图10.5类似，只是规模大些。图10.7中有200个元胞，初始状态随机设置，应用的更新规则是110，逐行往下更新了200时间步。图10.8应用的则是规则30，也是从随机初始状态开始。
1701066868
1701066869
1701066870
1701066871
1701066872
▲图10.7 规则110的时空图。这个一维元胞自动机有200个元胞，图中是从随机初始状态开始，200时间步的变化情况
1701066873
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.自然界中各种过程实现的计算在复杂程度上都几乎等价。