1701066890
1701066891
类型4：最有趣的类型。沃尔夫勒姆这样描述：“类型4是有序与随机的混合： [154] 局部结构相当简单，但是这些结构会移动，并以非常复杂的方式相互作用。”规则110（图10.7）就属于这一类。
1701066892
1701066893
沃尔夫勒姆猜想，由于图样和相互作用的复杂性，类型4的所有规则都能进行通用计算。不过很难证明某个具体的元胞自动机、图灵机或其他机器是通用的。图灵证明的只是存在通用图灵机，冯·诺依曼也只是证明自复制自动机同时也是通用计算机。后来有几位科学家证明了简单的元胞自动机（比如生命游戏）是通用的。20世纪90年代，沃尔夫勒姆的一位研究助手库克（Matthew Cook）最终证明了规则110的确是通用的， [155] 这也许是目前已知的最简单的通用计算机。
1701066894
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
1701066924
第4点对我来说没有意义。我认为很有可能我的大脑支持通用计算（至少在我有限的记忆容量允许的范围内），而线虫的脑也（基本上）是通用的，但我不认为我们进行的计算在复杂程度上是等价的。
1701066925
1701066926
沃尔夫勒姆走得更远，他认为存在一个简单的类似元胞自动机的规则可以作为“宇宙的终极确定性模型” [158] ，这个原初元胞自动机的计算是存在的万事万物的源头。这个规则有多长呢？沃尔夫勒姆说：“我猜其实相当短。” [159] 但是到底多长呢？他说：“我不知道。也许三四行Mathematica程序。”小写的计算。
1701066927
1701066928
《新科学》在2002年出版后引起了轰动——很快就位居亚马逊网站的畅销书榜首，并在之后很久都留在畅销书榜中。沃尔夫勒姆为了这本书的出版成立了沃尔夫勒姆媒体公司（Wolfram Media），在书出版后这家公司进行了大规模的宣传活动。对这本书的看法分成两个极端：一些读者认为这本书棒极了，是革命性的；另一些人认为这本书盲目自大，缺乏实质和原创性[例如，批评者指出物理学家祖斯（Konrad Zuse）和弗瑞德金（Edward Fredkin）早在20世纪60年代就提出了宇宙是元胞自动机的理论 [160] ]。不管怎样，我们这些元胞自动机的爱好者都认为，《新科学》至少很好地宣传了元胞自动机。
1701066929
1701066931
第11章 粒子计算[161]
1701066932
1701066933
1989年我偶然读到物理学家帕卡德（Norman Packard）的一篇文章， [162] 写的是用遗传算法设计元胞自动机规则。我一下就被吸引住了，想自己也试试。当时因为繁忙，无暇顾及（我在写博士论文），但这个想法一直留在我的脑海里。几年后，论文完成了，我也在圣塔菲研究所找到了职位，终于可以有时间深入研究这个问题了。有个叫赫拉贝尔（Peter Hraber）的本科生当时在研究所逗留，想找点事情做，我就把他招进来协助我研究这个课题。很快一个叫达斯（Rajarshi Das）的研究生也加入我们，他当时在独立研究类似的课题。
1701066934
1701066935
类似于帕卡德的思想，我们想用遗传算法演化出能执行所谓的“多数分类 [163] （majority classification）”任务的元胞自动机规则。这个任务很简单：元胞自动机要能区分初始状态中是开状态还是关状态占多数。如果是开状态占多数，最后所有元胞就应当都变成开状态。同样，如果是关状态占多数，最后所有元胞就应当都变成关状态。（如果初始状态中开状态和关状态的数量一样多，就没有答案，但是可以让元胞的数量为奇数来避免这种可能。）多数分类任务有点类似于选举，是在大家都只知道最近邻居的政治观点的情况下预测两个候选人谁会赢。
1701066936
1701066937
多数分类问题对冯·诺依曼结构的计算机而言是小菜一碟。CPU只需要分别对初始状态中的开状态和关状态进行计数，同时在内存中记录计数值就可以了。计数结束后，从内存中读取数值进行比较，然后根据结果将元胞状态都设成开或关。冯·诺依曼结构的计算机可以轻松实现这个工作，因为它有随机存取存储器可以存储初始状态和中间值，还有中央处理器可以计数，进行最后的比较，以及将状态重设。
1701066938
1701066939
而元胞自动机则没有CPU和内存可以用来计数。它只有一个一个的元胞，每个元胞除了自己的状态就只知道相邻元胞的状态。这种情形其实也是对许多实际系统的理想化。例如，在大脑中，神经元只与其他少数神经元有连接，而神经元必须决定是否激发，以及以何种强度激发，使得大量神经元的整体激发模式能表示特定的感知输入。类似的，第12章我们还会看到，蚂蚁必须根据与其他少量蚂蚁的交互来决定做什么事情，让蚁群整体能够受益。
[
上一页 ]
[ :1.70106689e+09 ]
[
下一页 ]