通用细胞自动机

通用细胞自动机是一种细胞自动机，它像图灵机一样，展现出通用性。冯·诺依曼证明，由具有四个正交邻居和 29 种可能状态的单元格组成的自动机，能够模拟图灵机，对于大约 个单元格的某种配置 (Gardner 1983, p. 227)。

关于二维生命游戏外全域细胞自动机是通用的证明概要由 Berlekamp、Conway 和 Guy (1982) 以及 Gosper (Gardner 1983, pp. 250-253) 独立给出。大约在 2000 年，P. Rendell (Rendell, Adamatzky 2001) 在生命游戏中显式地实现了图灵机。虽然 Rendell 的机器可以通过简单地使其磁带无限长而变成“真正”的通用计算机，但他既没有注意到这一事实，也没有提供通用图灵机的实际构造。随后，在 2002 年 11 月 11 日，P. Chapman 构建了一个生命游戏模式，该模式实现了通用寄存器机的动作，从而明确证明了生命游戏是通用的。

更令人惊讶的是，即使是一维细胞自动机也可以是通用的。Wolfram (2002, pp. 644-656) 给出了一个 19 色通用一维次近邻细胞自动机的例子，其中使用 20 个单元格的块来表示被模拟的细胞自动机中的每个单元格。上面的例子分别展示了 19 色通用自动机模拟规则 90 和规则 30 的前几个步骤 (Wolfram 2002, pp. 646-647)。

Smith (1971) 表明，18 种颜色和最近邻一维规则可以是通用的，Lindgren 和 Nordahl (1990) 构建了一个 7 色最近邻通用细胞自动机。最令人惊奇的是，正如 Wolfram (2002, pp. 675-691) 所展示的那样，两种颜色和最近邻规则足以在一维细胞自动机中产生通用性。特别是，虽然证明过程绝非易事，但规则 110基本细胞自动机是通用的 (Cook 2004)。

Gacs (2001) 已经证明，存在容错通用细胞自动机，只要这些扰动足够稀疏，它们模拟其他细胞自动机的能力就不会受到随机扰动的阻碍。