Question

rule 110 是另一个细胞自动机，由 Stephen Wolfram 在 1983 年提出。与 Conway 生命游戏里每个单元要么是生的要么是死的类似，rule 110 操作的单元按一维排列而不是二维网格形式。这意味着每个单元只有两个邻居而不是围绕着每个生命游戏单元的 8 个邻居。

在 rule 110 自动机的每一步，一个单元的下一个状态是由它自身的状态和它两个邻居的状态决定的。与生命游戏里规则都是通用的而且可以应用到生和死单元不同，rule 110 自动机对每一种可能都有一个单独的规则：

如果我们读取应用这 8 个规则之后的值，把一个死单元当成 0，把一个生单元当成 1，就可以得到二进制数 01101110。再转换可以产生十进制数 110，这就是这个细胞自动机名字的由来。

rule 110 比生命游戏简单得多，但它同样有复杂行为的能力。下面是一台 rule 110 自动机从一个简单生单元开始的前几步：

这个行为已经明显不简单了（例如，它不只是在生成一行固定的生单元），而如果运行同样的自动机 500 步，我们就可以看到有趣的模式：

此外，从一个包含生死单元的随机模式开始运行 rule 110，能够揭示所有形状的活动以及它们彼此之间的交互：

从这 8 条简单规则中浮现出来的复杂性被证明是非常强大的：2004 年，Matthew Cook发表了一个对 rule 110 事实上通用的证明。这个证明包含大量的细节（参考 http://www.complex-systems.com/pdf/15-1-1.pdf 的第 3 节和第 4 节）。但粗略地讲，它引入了几个不同的 rule 110 模式扮演“滑翔机”的角色，然后通过用一种特定的方式排列那些“滑翔机”来展示如何模拟任意循环标签系统。

这意味着 rule 110 可以运行一个循环标签系统的模拟，而循环标签系统又可以运行一个普通标签系统的模拟，普通标签系统可以运行一个通用图灵机的模拟。这不是完成通用计算的高效方式，但对这样一台简单的细胞自动机来讲仍然是一项令人印象深刻的技术成果。