算法编码定理

短程序至少贡献一块大的概率质量，所以“短描述”容易推出“概率不太小”。困难在反方向：许多较长程序可能一起给某个输出贡献很大质量，为什么这也会迫使它拥有某个短程序？

答案是把已经确认的累计质量当成可用的编码预算。质量每跨过一个二进阈值，就请求一条相应长度的码字；所有输出、所有阈值的总代价仍然有限，因此能统一装进一台前缀机。

两边不等式分别做什么 ​

最短程序本身在和式里，所以 $m_U(x)\ge 2^{-K(x)}$，从而 $-{\log }_2{m}_U(x)\le K(x)$。

反方向从 $m$ 的单调下逼近开始。对整数 $k\ge 0$，当首次发现 $m_s(x)>2^{-k}$ 时，为 $x$ 枚举一个长度 $k+2$ 的编码请求，每个 $(x,k)$ 只请求一次。对固定 $x$，所有满足 $2^{-k}<m(x)$ 的阈值权重和小于 $2m(x)$，于是全部请求预算满足

Kraft–Chaitin 编码定理公理库前缀复杂度与 Levin–Schnorr 定理Prefix-free Kolmogorov complexity · Levin–Schnorr theorem · Kraft–Chaitin theorem · 前缀 Kolmogorov 复杂度构造通用前缀机与 Kraft–Chaitin 在线编码，证明无限序列的 Martin-Löf 随机性等价于所有前缀的压缩亏损有统一常数界。把这些请求变成同一台前缀机。取 $k=\lfloor -{\log }_{2}m(x)\rfloor +1$，则 $2^{-k}<m(x)$，请求最终出现，故

严格阈值避免在 $m(x)$ 恰为二进分数时等待一个永远不会发生的“达到极限”事件。常数预算浪费无妨，不能浪费一个随 $x$ 增长的因子。

一次真实的阈值过程 ​

假设某个输出的下逼近依次为 $0.04,0.09,0.18$，最终趋于 $0.20$。首次超过 $1/32$ 时有长度 $7$ 的请求；超过 $1/16$ 时有长度 $6$ 的请求；超过 $1/8$ 时有长度 $5$ 的请求。它永远不超过 $1/4$，所以这个规则不发长度 $4$ 的请求。较早的长码字无需撤回，预算已经把它们都算进去。

这不是计算 $m(x)$ 后再取对数的算法。过程只等待可证实的下界，因此即使 $m(x)$ 不可计算也能工作。

与 Shannon 编码及普通复杂度的边界 ​

Shannon 编码从给定分布设计平均码长；这里是对每个对象的最短有效描述作逐点比较，而且通用半测度通常不可计算。定理不提供一台能输入 $x$ 就找到最短程序的压缩软件。

还必须使用前缀复杂度 $K$。若把右边换成普通复杂度 $C$，程序权重可能不满足 Kraft 预算，上述证明断裂。若把离散算法概率换成“无限输出以前缀 $x$ 开始”的树半测度，也需要相应的单调复杂度理论，不能直接照搬这个等式。

对任何下半可计算离散半测度 $\nu$，通用支配给出 $K(x)\le -{\log }_2\nu (x)+O_{\nu }(1)$。一个有效生成机制若把可观质量集中在某个结果上，该结果便不能一直具有极大的前缀复杂度。

但 $O(1)$ 不能被当成零，也不对任意改选机器保持同一个数值。比较极短字符串的具体复杂度时，机器选择可能淹没主要差别；定理最可靠的内容是统一加法常数下的关系。