Question

1970 年，John Conway 发明了一个叫作生命游戏（Game of Life）的通用系统。“游戏”要在一个无限多的二维网格里进行，网格的每个小方格可以是生或是死。一个小方格有 8 个邻居：它上面的三个单元，紧挨着它的左右两个单元，以及它下面的三个单元。

生命游戏像有限状态机那样分一系列步骤进行。在每一步，根据由这个单元自身的当前状态和它邻居的状态所触发的规则，每个单元都可能从生转变为死，或者相反。规则很简单：如果一个活着的单元有少于两个（人口稀少）或者多于三个（人口过剩）活着的邻居，它就会死掉，如果一个死的单元恰好有三个活着的邻居它就能复活（繁殖）。

下面是生命游戏规则如何通过一步的进程来影响一个单元状态的 6 个例子 11，生的单元用黑色表示，死的单元用白色表示：

11512 种可能：包括 9 个单元，并且其中每个单元可以是两种状态中的一个，因此有 2 × 2 × 2 × 2 ×2 × 2 × 2 × 2 × 2 = 512 种不同的可能。

像这样的一个系统，称为细胞自动机，包括一个单元组成的数组和在每一步更新一个单元状态的规则集合。

就像本章我们已经看到的其他系统一样，尽管规则简单，但生命游戏展示了出乎意料的复杂性。特定模式的生的单元会出现有趣的行为，其中最著名的就是滑翔机（glider），这是一个 5 个生单元的组合，每经过 4 步它们就会沿对角线移动一个方格：

目前已经发现了很多有意义的模式，包括用不同方式移动的网格形状（spaceship）、产生一连串的其他形状（gun），或者甚至产生它们自身的完整复制品（replicator）。

1982 年，Conway 除了展示如何靠以创造性的方式碰撞“滑翔机”来设计逻辑上的与门（AND）、或门（OR）和非门（NOT）以执行数字计算之外，还展示了如何使用一连串的“滑翔机”来表示二进制数据。这些结构说明理论上可以用生命游戏模拟一个数字计算机，但 Conway 没有设计出来一台可工作的机器。

到这里，构造一台任意的大型有限（同时非常慢！）的计算机只是一个工程问题了。我们的工程师已经给出了工具——让他来完成这项工作吧！ [……] 我们已经模拟的这种计算机从学术上被称为通用机器，因为它可以编程执行任何想要的计算。

——John Conway，《稳操胜券》（Winning Ways for Your Mathematical Plays）

2002 年，Paul Chapman 实现了一个特种通用计算机（http://www.igblan.free-online.co.uk/igblan/ca/）。而 2010 年，Paul Rendell 构造出了一台通用图灵机（http://rendell-attic.org/gol/utm/）。

下面是一小部分 Rendell 设计的特写：