规则

预设：

工作原理

一个 初等细胞自动机 是一维的细胞网格，每个细胞处于开或关状态。每一步中，细胞的下一个状态由当前状态和两个邻居决定——3个细胞的邻域有8种可能模式。

A 规则编号 （0-255）编码哪些模式产生「开」状态细胞。因为有8种可能的3细胞模式，每种可映射为开或关，所以有28 = 256种可能的规则。

上方图示展示了每条规则的8种情况。上排是输入模式（左邻居、本细胞、右邻居），下方是输出。

一些著名规则：

  • Rule 30 — chaotic, used in Mathematica's random number generator
  • Rule 90 — produces a Sierpinski triangle
  • Rule 110 — proven Turing-complete
  • Rule 184 — models traffic flow

与康威生命游戏的联系

这些一维自动机是与以下最简单的同族成员： 康威生命游戏. Life is a 2D cellular automaton where each cell has 8 neighbors instead of 2, and the rule considers the count of live neighbors rather than the exact pattern. But the core idea is identical: simple local rules produce complex global behavior. Rule 110's Turing-completeness shows that even the 1D case is capable of arbitrary computation.

沃尔夫勒姆的四类分类

斯蒂芬·沃尔夫勒姆根据长期行为将256条初等规则分为四类。这表明即使最简单的规则——一维、两种状态、最近邻——也能产生从平凡一致到通用计算的完整谱系。

第一类——均匀

演化导致均匀状态。无论初始条件如何，所有细胞变为相同。

第二类——周期

演化导致稳定或周期性重复结构。

第三类——混沌

演化产生伪随机、非周期模式。

第四类——复杂

局部结构出现并以复杂方式互动。能够进行通用计算。

The progression from Class I to Class IV mirrors a phase transition: too little activity produces uniformity, too much produces chaos, and the boundary between order and chaos — Class IV — is where complex, computation-capable behavior appears. Rule 110, a Class IV rule, has been proven Turing-complete, meaning it can simulate any computation given sufficient time and space.

另见

  • Life Garden ——二维细胞自动机（康威生命游戏）