规则 110

规则 110 是斯蒂芬·沃尔弗拉姆在 1983 年引入的基本元胞自动机规则之一（Wolfram 1983, 2002）。它指定单元格中的下一个颜色，取决于其颜色及其直接邻居。其规则结果以二进制表示形式编码为 。上图展示了此规则以及它在 15 步后产生的单个黑色单元格的演变过程 (OEIS A075437; Wolfram 2002, p. 55)。

上图展示了规则 110 的 250 次迭代。

镜像规则是规则 124，补集规则是规则 137，镜像补集规则是规则 193。

从单个黑色单元格开始，连续世代由解释数字 1, 6, 28, 104, 496, 1568, 7360, 27520, ... (OEIS A117999) 的二进制形式给出。省略尾随零（因为三角形的第 步中的右侧 个单元格始终为 0）得到序列 1, 3, 7, 13, 31, 49, 115, 215, 509, 775, 1805, ... (OEIS A006978)，这些数字只是前一个数字除以 ，对应的序列是 1, 11, 111, 1101, 11111, ... (OEIS A070887)。

令人惊讶的是，规则 110 元胞自动机是通用的，正如 Wolfram (1986, pp. 485-557) 最初推测的那样，随后由斯蒂芬·沃尔弗拉姆和他的助手马修·库克证明。这一重要发现源于 Wolfram 于 1985 年启动的旨在确立规则 110 通用性的计划。证明的主要要素在 1994 年到位，其他细节和更正持续了数年（Wolfram 2002, p. 1115; Cook 2004）。

规则 110 自动机对于特定初始条件的演变过程在 Wolfram (2002) 的封面上有所描绘，如 Wolfram (2002, p. 851) 中所述。