1701066840
四类元胞机
1701066841
1701066842
20世纪80年代初，普林斯顿高等研究院的物理学家沃尔夫勒姆对元胞机着了迷。沃尔夫勒姆（图10.4）是传奇般的天才人物。他1959年生于伦敦，15岁就发表了他的第一篇物理学论文。两年后，在牛津大学一年级的暑假，大部分人这时候都会去打工挣钱，或是背着背包搭顺风车周游欧洲，沃尔夫勒姆却写了一篇关于“量子色动力学”的论文，这篇论文被诺贝尔奖获得者物理学家盖尔曼注意到，他邀请沃尔夫勒姆加入他在加州理工的研究小组。两年后，沃尔夫勒姆获得了理论物理博士学位，而这时他才20岁（大部分人大学毕业后至少需要5年才能获得博士学位）。他留在加州理工任教，此后不久又获得了第一届麦克阿瑟天才奖。两年后，他受邀加入普林斯顿高等研究院。真是让人叹为观止。他有了名气，又有资金支持，可以想干什么就干什么，他决定研究元胞自动机动力学。
1701066843
1701066844
1701066845
1701066846
1701066847
▲图10.4 沃尔夫勒姆（照片由沃尔夫勒姆研究公司提供，Wolfram Research, Inc.）
1701066848
1701066849
根据理论物理学的惯例，沃尔夫勒姆从元胞自动机最简单的形式来研究其行为，他用的是一维两状态的元胞自动机，每个元胞仅与两个相邻元胞相连[图10.5（a）]。沃尔夫勒姆称之为“初等元胞自动机（elementary cellular automata）”。他认为，如果这种看上去极为简单的系统也理解不了，就更不可能理解更复杂的（例如，两维或多状态的）元胞自动机。
1701066850
1701066851
图10.5描绘了一个初等元胞自动机的规则。图10.5（a）是元胞格子——一排元胞，每个都与两侧相邻的元胞相连。这里仍然是用方格表示元胞——黑表示开，白表示关。两头的格子回绕连在一起，形成一个环。图10.5（b）是元胞遵循的规则：3个相邻元胞总共有8种可能状态组合，对于每种状态组合都给出了中间元胞的更新状态。例如，当3个元胞都是关状态时，中间元胞下一步就是关状态。同样，当3个元胞的状态为关—关—开时，中间元胞下一步就会变成开状态。这里规则指的是整个状态组合和更新状态的表，而不仅仅是表中的一行。图10.5（c）展示了这个元胞自动机的时空图。最顶上一行是一维元胞机的初始状态设置。下面跟着的依次是每一步更新后的状态。这种图被称为时空图，因为它表现了元胞自动机的立体构型随时间的变化。
1701066852
1701066853
1701066854
1701066855
1701066856
▲图10.5 （a）一维元胞自动机，两端回绕形成一个环；（b）初等元胞自动机的一种规则（规则110），表示3个元胞的状态组合以及对应的中间元胞下一步的状态；（c）时空图，显示了元胞自动机的4步变化
1701066857
1701066858
3个元胞有8种可能的状态组合[图10.5（b）]，而每种可能的状态组合又有两种可能的元胞更新状态，因此初等元胞自动机总共有256（2 8 ）种可能的规则。20世纪80年代时，计算机的性能已经足以让沃尔夫勒姆对这些规则逐个进行研究，设定各种初始状态，然后观察它们的变化。
1701066859
1701066860
沃尔夫勒姆给初等元胞自动机的规则都编了号，编号方法见图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”。（注释中介绍了如何将二进制数转换为十进制数。 [151] ）
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）就属于这一类。