TAOCP 第 4B 卷 习题 76：周期 3 可动生命振荡器

研究工作台 · 最后更新：2026-04-15

一、问题本身

Donald Knuth 在《计算机程序设计的艺术》第 4B 卷 第 7.2.2.2 节（可满足性）习题 76（位于第 322 页）中写道：

76. [41] 构造一个周期为 3 的可动（mobile）生命振荡器。

难度值 [41] —— 在 Knuth 的难度体系中属于"较难的研究性问题"，通常意味着 截至书籍出版时，作者本人尚未掌握完全令人满意的解答，鼓励读者投入 长时间的研究去攻破或改进已有结果。

1. 相关定义（第 4B 卷第 202–203 页）

生命路径（Life path）：Conway 生命游戏按演化规则给出的 一列位形 X₀ → X₁ → … → X_r。

可动生命路径（mobile Life path）：在生命路径之上附加 "任何一个格子都不能连续存活超过 4 个时间步"的约束。 用合取范式（CNF）写，对任意格子 (i,j) 和任意 0 ≤ t ≤ r−4：

(¬x_{t,i,j} ∨ ¬x_{t+1,i,j} ∨ ¬x_{t+2,i,j} ∨ ¬x_{t+3,i,j} ∨ ¬x_{t+4,i,j})

这等价于要求每个活细胞每 5 步之内必须"休息"至少一次。 约束强制图案具有结构性的"流动"，从而排除那些靠原地不动取胜的振荡器。

周期 p 的可动振荡器：一条可动生命路径， 满足 X_p ≡ X₀（即 p 步之后 回到初始位形），并且是有限的（任何时刻只有有限多个活细胞）。

2. 为什么"周期 3"特别有趣

生命规则本身带有强烈的二值对称性，使周期 2 的结构（flipflop） 相对容易构造；习题 73、74 已给出若干 mobile flipflop 的例子。 但周期 3 在拓扑和组合结构上陡然变难：

• 习题 75（Stephen Silver, 2000）已证明：对任何 p ≥ 3 的 可动振荡器，必然存在某个格子在一个周期内被激活超过一次。 这是一个非平凡的结构性限制，排除了"每格最多亮一次"的朴素构造。
• 周期 3 的可动约束要求每个活细胞必定在三步中至少死一次， 但又不能死得太多以致图案消散，留给设计者的自由度极窄。

二、目前的 State of the Art

习题 76 并非完全开放——已有若干已知解，构成当前的"前沿"：

1. 最小已知有限解：Jason Summers, 2012

Knuth 给出的答案（第 564 页）写道：

目前已知最小的实例是 Jason Summers 在 2012 年发现的一个 28 × 33 图案。此处用字母 {F, A, B}、{B, C, D}、{D, E, F} 分别标记在 t mod 3 = 0、1、2 时刻活着的细胞。 他巧妙的构造特别地给出了一个基于 7 × 24 环面的 无穷解。此外，还存在一个令人惊叹的 7 × 7 环面上的无穷解，但除此之外所知甚少。

Summers 的 28 × 33 构造利用三色图示（对应三个时间相位）实现了 一套精巧的"信号接力"：每个活细胞在一个周期内的存活时长严格 满足 ≤ 4 的可动性约束，同时周围邻居恰好满足生命规则对 生存与诞生的要求。该构造是全文目前唯一公开的有限周期 3 可动振荡器，构造细节见本工作台 problem/answer-76-and-context.txt。

2. 已知的环面（无穷）解

• 7 × 24 环面：由 Summers 的有限构造自然剥离出来， 可视为其"基础瓷砖"在纵向无限重复。
• 7 × 7 环面：一个独立发现的、令人惊讶的小尺寸 解；Knuth 称之为 "amazing"（惊人的），因其面积远小于 7 × 24。

3. 尚未解决 / 值得研究的方向

三、姊妹题：习题 68 与 Chaffin 的解答

1. 习题 68 是什么

第 322 页的习题 68 [难度 39] 写道：

68. [39] 找出在任何时刻都有 6 到 10 个活细胞的 最长可动路径（mobile path）。

这里的"可动"与习题 76 是同一个概念 —— 每个格子不得 连续存活超过 4 步。区别在于：习题 68 求的是有限长度 的单向路径（起于 X₀，终于某个 X_r，不要求循环）， 并且对同时存活细胞数加了一个 6–10 的窗口约束； 而习题 76 求的是周期 3 的闭合循环（X₃ ≡ X₀）， 没有对活细胞数的窗口约束，但必须是闭合的、且难度整整高了 2 档 [41]。

2. Chaffin 的解答（2026 年勘误）

Knuth 为第 4 次印刷准备的勘误（source/err4b-current.textxt 第 4b.561 页 amendpage，日期 2026-02-26）将习题 68 的答案整段替换为 "Solution by Ben Chaffin"：

用位运算做穷尽枚举是可行的（而且不需要 SAT 求解器）。 起始活细胞数为 (6, 7, 8, 9, 10) 时，可达的最长可动路径代数分别为 (8, 9, 10, 11, 11)；达到长度 11 的起始图案已在答案中给出。 大致 (69%, 8%, 10%, 4%, 13%) 的全部起点最终以 （死绝、过活、停止可动、静物、越出边界）结束。

Chaffin 的名字因此进入第 4B 卷的索引。

3. 与习题 76 的关系

68 与 76 之间有多重联系，这正是我们应当先仔细研究 68 的原因：

• 共享核心约束：两题使用的"可动"约束完全相同 （任何格子不得连续活过 4 步）。任何为 68 写的状态表示、转移枚举、 可动性判定都可以直接或几乎直接复用到 76。
• 方法论的权威背书：68 原本是一道被视为需要 SAT 的题，但 Chaffin 证明了位运算 + 穷尽枚举即可解决， 并被 Knuth 正式收录。这给 76 提供了明确的攻击路径： 位运算 + 对称性约简 + 智能剪枝的穷尽枚举， 而非一上来就编码 SAT。本工作台沿此路径展开，SAT 仅作为交叉验证。
• 结局分类的启示：Chaffin 对 (too dead, too live, immobile, still, out-of-bounds) 五种结局的统计，对 76 直接有用 —— 在 76 中我们要找的恰好是那个"4% 静物"与"10% immobile" 的边缘地带的反面：不静、仍可动、且闭合回到起点。
• 路径长度的上界线索：68 告诉我们在 6–10 活细胞 窗口内，最长只能走 11 步。若将活细胞数窗口放宽，最长可达多少 仍然开放 —— 而 76 要求的闭合周期 3 本质上是"只走 3 步并回到起点" 这一非常强的约束，与 68 的"走尽可能长"正好是对偶方向。
• 工程上的"热身"作用：在正式进攻 76 之前， 用自己的代码复现 Chaffin 的 (8, 9, 10, 11, 11) 结果与各结局百分比， 是验证位运算引擎正确性的绝佳基准。若复现一致，则引擎可直接 升级去枚举周期 3 循环。

换句话说：68 是 76 的"侦察演习" —— 同一套工具、同一种约束、更小的搜索空间、已有答案可对照， 先把 68 彻底打穿，再转身攻 76。

四、"胜利"的几个层次（按雄心递减）

1. A 级：找到严格小于 28 × 33 的有限可动周期 3 振荡器 —— 几乎确定能得到 Knuth 的致谢与索引条目。
2. B 级：证明非平凡的有限振荡器外接矩形下界 —— 高价值的理论贡献。
3. C 级：发现新的环面解（例如 7 × N 的其他 N， 或非 7 行的情况）—— 有分量的新结果。
4. D 级：通过穷尽搜索证明在某尺寸以下不存在解 —— 即使部分结果也有价值。
5. E 级：对 Summers 构造的独立、干净、可验证的复现。
6. F 级：改向攻击周期 4 或 5。

五、参考资料指引

• source/vol4b.pdf / vol4b.txt —— 已出版的正书。
• source/fasc6a.pdf —— 早期预分册，同样的生命题材。
• source/err4b-current.textxt —— Knuth 最新官方勘误 （含 Chaffin 的习题 68 解答，位于 4b.561）。
• problem/section-7.2.2.2-life-text.txt —— 第 7.2.2.2 节 生命路径的正文。
• problem/exercises-65-85-life-sat.txt —— 习题 65–85 全文。
• problem/answer-76-and-context.txt —— 习题 76 答案及 Summers 构造的 ASCII 图示。

—— 研究由 Shisheng Li（daizisheng@gmail.com）主持， 延续其在 TAOCP 未决问题上的一贯路线：穷尽枚举 + 对称性约简 + 字面程序式呈现。