1701066811
同其他许多精彩的思想一样，元胞自动机也是由冯·诺依曼发明的，他在20世纪40年代受他的一位同事——数学家乌拉姆——的启发提出了这个思想。（为了与冯·诺依曼体系结构相区别，元胞自动机经常被称为非冯·诺依曼体系结构，这是计算机科学的一大笑话。）第8章说过，冯·诺依曼想要将自我复制机器的逻辑形式化，而他用来研究这个问题的工具就是元胞自动机。简单地说，他设计了一种元胞自动机规则，能完美复制任意元胞自动机的初始形态，他的规则中元胞不止两种状态，而是29种。
1701066812
1701066813
冯·诺依曼还证明他的元胞自动机等价于通用图灵机（参见第4章）。元胞的更新规则扮演了图灵机读写头的规则的角色，而元胞阵列的状态则相当于图灵机的带子——也就是说，它可以编码通用图灵机运行的程序和数据。元胞一步一步地更新相当于通用图灵机一步一步地迭代。能力等价于通用图灵机的系统（也就是说，通用图灵机能做的，它也能做）被称为通用计算机，或者说能进行通用计算。
1701066814
1701066815
复杂 [:1701064780]
1701066816
生命游戏
1701066817
1701066818
冯·诺依曼的元胞自动机规则相当复杂。1970年，数学家康威（John Conway）发现了一种简单得多的两状态通用图灵机，也能进行通用计算。他称之为“生命游戏”。 [148] 我不知道为什么叫作“游戏”，只知道“生命”来自于康威对其规则的解释。将状态为开的元胞看作活的，状态为关的元胞看作死的。康威用四种生命过程来定义规则：出生，死元胞的相邻元胞中如果刚好有3个是活的，下一步就变成活的；存活，活元胞的相邻元胞有2—3个是活的，下一步就能继续存活；过于稀疏，活元胞的相邻活元胞如果少于2个就会死去；过度拥挤，活元胞的相邻活元胞如果多于3个就会死去。
1701066819
1701066820
康威当时是想寻找一个能产生类似生命的元胞自动机。出人意料的是，生命游戏的行为丰富而有趣，以至于现在出现了一个爱好者团体，他们的主要兴趣就是发现能产生有趣行为的初始设置。
1701066821
1701066822
图10.3就是其中一个有趣的行为，被称为滑翔机。这里我们不再用灯泡，就用黑格子表示开（活），用白格子表示关（死）。图10.3中可以看到有一个滑翔机向东南方向移动。当然，元胞并没有动，它们都是固定的。移动的是由活状态元胞形成的一个不消散的形状。因为元胞自动机的边界是回绕相连的，所以滑翔机能一直移动。
1701066823
1701066824
1701066825
1701066826
1701066827
▲图10.3 生命游戏中滑翔机的一个循环变化。滑翔机形状每4步向东南方向移动一格
1701066828
1701066829
爱好者们还发现了其他复杂的形状，例如太空船，它类似于滑翔机，而且更有趣；滑翔机发射器，它会不断射出新的滑翔机。康威证明，通过用变化的开/关状态模拟读写头在带子上的读写，就能让生命游戏模拟图灵机。
1701066830
1701066831
康威还给出了生命游戏模拟通用计算机的证明框架 [149] （后来由其他人细化）。 [150] 将程序和输入数据编码为开关状态初始设置，生命游戏运行后产生的图样表示程序的输出。
1701066832
1701066833
康威在证明中组合使用滑翔机发射器、滑翔机等结构来实现与、或、非等逻辑运算。人们早已发现，能用各种可能来组合这些逻辑操作的机器就能进行通用计算。康威的证明表明，原则上，逻辑运算的所有可能组合都能在生命游戏中实现。
1701066834
1701066835
像生命游戏这么简单的元胞自动机在原则上能运行标准计算机运行的程序，这真是让人吃惊。不过，实际上，稍微复杂一点的计算就需要大量逻辑运算，并以各种方式相互作用，因此要设计出能实现复杂计算的初始设置基本不太可能。即使设计得出来，计算也会慢得让人无法忍受，更不要说用这种并行的非冯·诺依曼结构的元胞自动机来模拟传统冯·诺依曼结构计算机需要耗费的大量资源。
1701066836
1701066837
因此没有人用生命游戏（或其他“通用”元胞自动机）来进行真实计算或是模拟自然系统。我们只是想利用元胞自动机的并行特征以及它产生复杂图形的能力。下面先来看看元胞自动机能够产生的图形种类。
1701066838
1701066839
复杂 [:1701064781]
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] ）