规则110——一个通用元胞自动机
这不是图灵机，而是一个可计算通用的系统，简单得几乎令人难以置信。
基本设定。 一排一维排列的元胞，每个取值为 0/1，并行更新：每个元胞的下一个值只取决于它自己和左右两个邻居（2³ = 8 种输入模式）。把这 8 种输出按二进制字节编号，就得到了这条规则的名字——规则110就是其中一个具体的字节。
Cook（源自 Wolfram）：规则110是图灵完备的通过编码彼此碰撞、从而携带并处理信息的"滑翔机"（gliders，移动的模式），规则110可以模拟任意图灵机（借助循环标签系统，cyclic tag systems）。
为什么它如此出名。 它是已知最简单的通用系统之一——一条固定的8位局部规则，没有状态，没有读写头，只有并行的邻居更新——却能实现完整的计算。它是 Wolfram 论题的头号证据：通用性（以及不可判定性）是常态，而非例外——即便看起来微不足道的动力学系统，也可能是计算通用的，因而带有不可判定的长期行为问题。