另一个以科学的严肃态度对待复杂性的传奇人物是斯蒂芬·沃尔夫勒姆（见图13-1）。他年轻时是个神童，20岁就从加州理工学院获得了物理学博士学位，创造了该学位最年轻毕业生的纪录，并于1986年在伊利诺伊大学成立了复杂系统研究中心。沃尔夫勒姆认为神经网络过于复杂，于是决定转变研究方向，开始探索细胞自动机。

图13-1　斯蒂芬·沃尔夫勒姆在他位于马萨诸塞州康科德的家中，站在由算法生成的地板上。沃尔夫勒姆是复杂性理论的先驱，他曾经提出，即使是简单的程序也会生成现实级别的复杂性。图片来源：斯蒂芬·沃尔夫勒姆。

细胞自动机通常只有少数几个随时间变化的离散值，这取决于其他细胞的状态。最简单的一种细胞自动机，是一组一维的细胞阵列，每个细胞的值为0或1（见方框13.1）。“生命的游戏”（Game of Life）也许是最著名的细胞自动机了，它是由普林斯顿大学的数学教授约翰·康威（John Conway）在1968年发明的，并由马丁·加德纳（Martin Gardner）通过他在杂志《科学美国人》（Scientific American）的“数学游戏”专栏中推广开来（见图13-2）。整个空间是一个二维的细胞阵列，细胞只有“开”或“关”的状态，对规则的更新仅取决于4 个最近的相邻细胞。在每个时间步骤中，所有细胞的状态都会更新。阵列中会生成复杂的模式，其中一些模式还有自己的名字，例如“滑翔机”，它会横跨阵列并与其他模式发生碰撞。初始条件对于找到显示复杂模式的配置至关重要。

生成复杂系统的规则有多普遍呢？沃尔夫勒姆想要了解可能导致复杂行为的最简单的细胞自动机规则，于是他开始从所有规则中寻找。规则0～29 产生的模式总是会回归枯燥的行为：所有的细胞都会以重复模式或嵌套分形模式结束。但是，规则30 产生了展开模式，规则110 不断变化并演变出了复杂模式（见方框13.1）。8 最终证明，规则110 能够实现通用计算；也就是说，所有可能的细胞自动机中，最简单的一些已经具备了可以计算任何可计算函数的图灵机的能力，所以它在原则上与任何计算机一样强大。

13.1

细胞自动机(www.daowen.com)

规则110。细胞自动机的运行规则是：细胞的颜色依据自身和直接相邻的细胞的颜色而改变。例如，对于图片顶部3 个细胞的黑色和白色的8 种可能组合，规则110 指定了其下方细胞的颜色。这条规则的演变能够每次对一行细胞进行更新，从第一行的单个黑色细胞开始，更新15 次后，就产生了中间的那幅图，而更新了250 次后，则产生了底部的那幅图。简单的初始条件演变成了一个无限延续的非常复杂的模式。这其中的复杂性来自哪里？想了解更多细节，请参阅：http：//mathworld.wolfram.com/Rule 110.html。

图13-2　生命的游戏。一个Gosper滑翔机枪（图片顶部）的快照，它发出一系列按对角线飞行的滑翔机图标，从“母船”（顶部）飞往右下角。图片来自维基百科：Gun（cellular automaton），有一个滑翔机枪运动的GIF动画。

该发现的一个意义在于，我们在生命体中发现的显著复杂性，可以通过对分子间化学相互作用的最简空间进行采样，从而实现演化。而演化过程中出现的复杂的分子组合，应该是能够预料到的，不应该被当作是什么奇迹。但细胞自动机可能不是早期生命的优秀模型，究竟哪些简单的化学系统能够产生复杂的分子结构，仍然是一个悬而未决的问题。9 也许只有特殊的生物化学系统才有这种特性，这有助于减少可能产生生命的潜在相互作用种类的数量。

生命的一个重要特性，是细胞的自我复制能力。匈牙利裔美国数学家约翰·冯·诺依曼，曾经于20 世纪40 年代在普林斯顿高级研究所使用细胞自动机探索过这种能力。冯·诺依曼的工作对数学的许多领域都产生了重大影响，特别是他关于博弈论的开创性工作（在第1章中提到过）。在寻找可以完全自我复制的最简单的细胞自动机过程中，冯·诺依曼发现了一个复杂的细胞自动机，具有29 个内部状态和一个大型的记忆体，可以实现自我复制。10该发现具有重大的生物学意义，因为能够自我复制的细胞中，也有许多内部状态和记忆以DNA的形式存在。从那以后，更简单的、能够自我复制的细胞自动机陆续被发现。