安全递归定理（内核形态）

上级：recursive-harness

为什么不用原始递归

三类递归支配着任务委派：

• primitive-recursion（原始递归）= 结构上有界的循环：循环体作用于一个语法上更小的对象（列表变短、树往下走），因此终止性在语法层面就有保证。安全、可证明终止——但也可证明太弱（无法表达 Ackermann 函数）。对委派而言，这是一个关键限制：一个庞大任务的深度事先未知，因此一个被限制在原始递归内的管理者甚至无法表达出这个计划。

• general-recursion（一般递归，μ 算子）= 完整的图灵能力。任何"以任何方式可计算"的函数都可以用递归来计算。终止性不可判定（halting-problem）。没有人会把一个庞大任务交给单个无界循环去做，无论它多聪明：你无法保证它会结束，无法控制预算，也没有办法介入。

• 第三条路 = 良基递归（well-founded recursion）：允许任意非结构性的递归，但要求存在一个终止度量（一个在每一步递归中必须严格递减的量），并且它递减进入一个良基序（不存在无穷下降链）。这正是 Lean 接受非结构性递归的方式（termination_by 子句），也正是 pc-well-founded-recursion 以 P×C 作为度量所做的事——失败概率乘以失败代价，在可接受时停止，而每一次分解都必须降低 P×C。

设定

一个任务是树上的一个节点。执行者有两个可能出错的动作：

• SOLVE（求解） 一个叶子节点，直接给出结果——不精确，误差 ≤ $\varepsilon_{\mathrm{exec}}$；

• DECOMPOSE（分解） 成若干子节点加一个重组方案——这一步本身也可能出错：以概率 ≤ $\alpha_{\mathrm{split}}$ 拆分是错的（子节点合起来并不蕴含父节点），并且重组自身带有误差 $\varepsilon_{\mathrm{join}}$。

每个节点的产出物都要通过一道门（gate）（gate-theory）：其可靠性达到误接受率 $\alpha$、容差 δ 的水平。这道门同时检查度量是否递减——每个子节点的 P×C 必须严格小于父节点的 P×C。

安全递归（软化的良基 μ）——内核形态

Theorem

设执行者把一个任务递归地分解成一棵由子任务和叶子构成的树。若 (i) 终止性：每一次分解，度量 P×C 都严格递减进入一个良基序（在门处得到验证）——因此这棵树是有限的，递归在初始预算内终止；(ii) 局部可靠性：每道门的通过都蕴含局部正确性达到 (δ, $\alpha$) 的水平，误接受按 gates-are-necessary-conditions 被削减；(iii) 误差收敛：每一步重组都是误差度量上一个收缩系数 k < 1 的压缩映射——子节点的误差被衰减而非放大（inexact-contraction）——那么根节点的产出物与正确解的偏差在 $\varepsilon/(1-k)$ 以内，成立概率至少为 $1 - \sum \alpha$（对所有门求和），且在初始 P×C 预算之内。

小结： 终止性 + 正确性 + 预算，三者都被软化了。

Proof

仅为证明草图——这些假设是设计上必须满足的义务，尚未针对真实 harness 做形式化验证。

对分解树做结构归纳，该树由 (i) 保证是有限的。基础情形（叶子）：由 (ii)，每个叶子的产出物以高概率在其局部容差 $\varepsilon_{\mathrm{exec}}$ 以内是正确的。归纳情形（内部节点）：由归纳假设，假定所有子树都产出了在各自界限内正确的产出物。重组步骤把这些已修正的子节点组合起来；由 (iii)，重组后的误差满足 inexact-contraction 的递推关系——来自子节点的误差被 k < 1 缩小，并且跨所有深度累积的误差收敛到 $\varepsilon/(1-k)$（而不是发散到无穷）。对各门误接受率 $\alpha$ 取联合界，就得到概率上界：任一门误接受的概率按 $\sum \alpha$ 的量级增长，因此正确性是高概率成立的。∎

控制必须控制自身

分解与委派不是凌驾于定理之上的元操作——它们是定理内部的、同样会出错的操作，有自己的 $\varepsilon$、自己的 $\alpha$、自己的门。计划本身就是一个产出物。

忘记这一点会导致一种特有的失败：一次错误的拆分（分解节点处的门接受了一个有问题的拆分），于是整棵子树完美地解决了一个错误的问题。每个叶子的门都是绿色的，每个子产出物内部都是正确的，而整体是错的。只有一道对照父节点 spec 做检查的重组门（而不是对照子节点的 spec）才能抓住它。

这不会退化成一座无穷的"控制器之控制器"高塔，因为整个 harness 都依赖一个不对称性：验证比生成便宜。 对控制输出做同一层级的门检查——一道检查某次拆分是否忠实于它所要分解的任务的门——是负担得起的。它不是在生成一个计划，而是在检查一个计划。

因此门存在于控制层级的每一层，而不只是在执行叶子处。叶子被检查是否符合 spec；拆分被检查作为一次分解是否正确；合并被检查是否与父节点一致；最终的根节点被对照最初的目标做检查。每一道门抓住的是该层特有的失败模式。

Ashby 式的回响。 这正是逐层的必要多样性：每一层的失败模式都是一类不同的扰动（错的叶子、错的拆分、错的合并），而 "唯有多样性才能消灭多样性" 要求为每一层配一个与之匹配的调节器——这正是为什么分层设门是结构性的，而不是装饰性的。那道对照父节点 spec 做检查的重组门，正是 good-regulator-theorem 的一个缩影：门内嵌了任务的模型（即 spec）——你无法调节你无法建模的东西。 而"不会退化"这一不对称性，正是 Ashby 意义上的放大器：用一个廉价、低多样性的检查去调节一个高多样性的生成，正是调节得以沿层级放大、而不是退化成控制器高塔的原因。

证明义务 → 引理

定理的假设分解成若干具体的引理，你必须为自己的 harness 逐一建立它们：

义务	证明于	含义
(i) 终止性： P×C 严格递减，趋向一个良基序	pc-well-founded-recursion	每一次分解都必须降低任务的失败概率—代价；分解门验证这一点；不可能出现循环
(ii) 局部可靠性： 每道门的通过都蕴含局部正确性 (δ, $\alpha$)	gates-are-necessary-conditions	一道门只放行它能认证的东西；误接受率 $\alpha$ 内在于门的验证方式；容差 δ 是一个设计选择
(iii) 误差收敛： 重组是一个收缩映射（系数 k < 1）	inexact-contraction	子产出物的误差不会累积；每一步重组都把它们缩小；极限是 $\varepsilon/(1-k)$
预算与容差的兑换	relaxation	给定的 P×C 预算能买到多少 $\varepsilon$？容差 δ 又如何计入代价？
可能出问题的地方	honest-caveats	度量 P×C 是真实风险的代理指标（Goodhart 定律）；各个 $\alpha$ 之间相关，因此 $\sum \alpha$ 是乐观估计；文本状态度量上的收缩性在实践中尚未得到证明

结语

一个庞大的任务可以安全地委派出去，不是因为模型足够聪明，而是因为递归是良基的、每一步动作——包括拆分本身——都设了门、并且重组是收缩的。