系统

Rule 30：一行逻辑，永远安定不下来

Rule 30 写得进一条公式：左 XOR（中 OR 右）。可是从一个黑格开始，它长出来的图案右半边看起来像杂讯。它为什么一边整齐一边乱、中间那一列怎么变成随机数、为什么那不等于密码学，以及它身上到现在还没解开的问题。

Rule 30 完全确定，实际上却无法预测。把规则知道得一清二楚，不等于知道它会走到哪里。

整条规则，就一行

和所有一维元胞自动机一样，Rule 30 用上一排的三个格子决定新格子：左、中、右。按标准顺序，答案是 111 得 0、110 得 0、101 得 0、100 得 1、011 得 1、010 得 1、001 得 1、000 得 0。把这些输出当成一个二进制数 00011110 来读，就是 30。256 条规则都怎么这样编号，写在《256 条规则，每条一个 byte》。

Stephen Wolfram 在 1983 年提出 Rule 30。整张表可以缩成一条公式：新格子等于左格 XOR（中格 OR 右格）。随便验一行：100 的中格和右格都是 0，结果就是左格，1；101 的右格是 1，结果是 1 XOR 1，等于 0。

左边整齐，右边杂乱

从一个黑格开始，图案长成一个三角形。左边的边缘很快排成规律的斜纹。右半边却从来没有安定下来：大大小小的三角形不停开开合合，看不出任何秩序。

公式解释了这种一边倒。因为新格子等于左格 XOR 某个东西，左格一变，结果就一定跟着变，所以每一个差异都会一路往右传、永远不会消失。这条规则左右不对称；它的镜像是 Rule 86，乱的那一边换到了左边。

一整列的抛硬币

现在只看中间那一格，一排一排往下读。这个序列开头是 1101110011000101，之后一直延续，看不出任何规律。前 4,000 排里，大约一半是黑格；00、01、10、11 四种相邻组合，各自大约占四分之一；也找不到短的重复周期。

Wolfram 在 1986 年那篇讲随机序列生成的论文里，提出的正是这种用法，而 Mathematica 也曾用 Rule 30 来产生随机整数。一条完全不含随机的规则，产生出来的一列数字，在很多统计检验里都能冒充抛硬币。奇怪的地方就在这里：这些混乱不是从外面加进来的，是算出来的。

看起来随机，不等于安全

Rule 30 的一切都是确定的。给同一排起点，每次都得到同一张图，所以它是伪随机，不是真随机。用在模拟、游戏、抽样上没问题，那些场合本来就想要可以重现的杂讯。

密码学要求的更多。Wolfram 在 1985 年提出过以 Rule 30 做的串流密码，1991 年 Willi Meier 和 Othmar Staffelbach 发表分析，说明这类产生器比看起来的弱。通过统计检验，只代表旁观者不容易看出规律；不代表攻击者找不到。

三个还没解开的问题

Wolfram 把这种行为叫做计算不可约（computational irreducibility）：要知道第一百万排长什么样，一般来说唯一的办法就是把前面每一排都算出来。连 Rule 30 最基本的性质，到现在都还没人证明。2019 年 10 月他设了三个各一万美元的奖金：中间那一列是不是永远不会变成周期性？黑格和白格平均下来是不是一样多？算出第 n 格，是不是真的至少要花和 n 同阶的步数？

一条写得进一行的规则，身上还挂着没人答得出的问题。大自然好像也在跑类似的东西：芋螺 Conus textile 的壳上，花纹看起来就很像 Rule 30。想亲身感受「知道规则」和「知道未来」之间的差距，最快的方法是在实验室输入 30，看它长出来。