量化不完备性——Chaitin 的信息界限

父级：relaxing-undecidability

哥德尔说某些真理是不可证明的。Chaitin 用比特为不完备性分级：一个理论无法证明任何对象比该理论自身更随机。

Chaitin 不完备性定理

设 K(x) 为 Kolmogorov 复杂度（生成 x 的最短程序）。对于一个一致、可靠、递归公理化的理论 T，其公理具有程序大小复杂度 c，存在一个常数，使得 T 能证明"K(x) > n"的 n 只有有限多个——本质上仅能证明到 n ≈ c + O(1)。

于是，一个信息量为 c 比特的形式系统无法证明超出 c 的随机性。不完备性由此变成一条守恒定律：可证明的复杂度受限于公理的信息含量。（[[probabilistic-undecidability|Ω]] 是极端情形——一条无穷的定理流，每一条都需要自己专属的公理。）

这一关联——正是证明领域中的 requisite variety（必要多样性）。 正如调节器所需的多样性必须不小于它要吸收的扰动，证明系统所需的信息量也必须不小于它所证明对象的复杂度。 你无法验证一个比你的证书语言更复杂的系统——验证带宽的天花板（relaxing-undecidability、certificates）正是 Chaitin 界限的另一种面目。