沃尔夫勒姆规则110

Wolfram的规则110是Stephen Wolfram「基本」规则分类中的一个卓越的一维细胞自动机。这个线性网格中的每个单元格可以处于两种状态之一：0（关）或1（开）。每一步，下一行单元格通过查看当前行的三元组来确定——每个单元格加上它的两个邻居。哪些三元组在下一代产生1的模式由二进制数110编码。

尽管定义极简——只有几个比特描述哪些局部排列变为「开」——规则110展示了令人难以置信的丰富和复杂的行为。在某些初始条件下，它已被证明是图灵完备的，与理论上可以执行通用计算的系统相当。

工作原理 →

规则

在基本细胞自动机术语中，十进制规则号110对应于从「111」三元组到「000」读取时的位模式01101110。这意味着某些三元组（如110、101、011、001）在下一代产生活细胞，而其他则产生死细胞。

尽管命名约定简单，出现的行为可能令人惊讶地复杂。您会看到由这些简单三元组规则驱动的混沌区域、重复模式和各种相互作用。

涌现与复杂性

规则110最有趣的方面之一是单行比特如何演化成看起来像移动粒子、碰撞或波前的结构。初始行的微小变化可以极大地改变展开的图案，突显了系统对初始条件的敏感性。这种涌现的复杂性纯粹来自局部相互作用——不需要中央协调。

在某些配置中，您会看到稳定区域、「Glider」以及重复或混沌的扩展，这强调了系统的深度。研究人员广泛研究了这个自动机，以理解简单的确定性系统如何可能表现出看似随机或至少计算上不可约的模式。

图灵完备性

规则110可以配置为计算通用图灵机能计算的任何东西，使其图灵完备。这意味着如果您以正确的方式设置初始行，理论上可以在这个小自动机内模拟逻辑运算、内存和任何基本计算元素。这是一个令人印象深刻的演示，表明即使从最简单的规则集中也能产生复杂性——随着时间的推移，重复的局部相互作用产生强大的行为。

算法概述

下面是计算每个新行的简单方法。我们可选地包装边缘，使一侧的单元格可以看到另一侧的邻居。如果禁用此功能，网格外的边缘被视为「死亡」：

// Rule 110 transition table - maps each 3-bit pattern to its next state
const transitions = {
  // pattern => next state
  '111': 0,
  '110': 1,
  '101': 1,
  '100': 0,
  '011': 1,
  '010': 1,
  '001': 1,
  '000': 0
};

以下是我们在每次更新时如何应用它（虽然我们的最终实现使用位移方法，但此表是哪些三元组产生活细胞的替代表达）：

function computeNextRow(currentRow, wrapEdges) {
  const length = currentRow.length;
  const newRow = new Array(length).fill(0);

  for (let i = 0; i < length; i++) {
    const leftIndex  = wrapEdges ? (i - 1 + length) % length : i - 1;
    const rightIndex = wrapEdges ? (i + 1) % length : i + 1;

    const left   = (leftIndex < 0 || leftIndex >= length) ? 0 : currentRow[leftIndex];
    const center = currentRow[i];
    const right  = (rightIndex < 0 || rightIndex >= length) ? 0 : currentRow[rightIndex];

    const pattern = (left << 2) | (center << 1) | right;
    newRow[i] = (110 >> pattern) & 1;
  }
  return newRow;
}