前缀复杂度与 Levin–Schnorr 定理

短程序占用一块较大的码树空间：长度 $r$ 的程序占用权重 $2^{-r}$。前缀条件使这些空间互不重叠，Kraft 不等式公理库Kraft–McMillan 不等式Kraft–McMillan inequality刻画给定码长集合存在前缀码或唯一可译码的必要充分不等式。便把“有多少短描述”转成概率预算。如果一个长度 $n$ 的前缀只需 $n-c$ 位描述，它所确定的柱集可以放进总质量至多 $2^{-c}$ 的有效异常集合。

反方向则把检验看成压缩资源。第 $2k$ 层最多占 $2^{-2k}$ 的质量；若把这一层每个柱集的描述缩短 $k$ 位，总代价至多 $2^{-k}$。所有 $k\ge 1$ 层的代价加起来仍不超过一，可以装进同一台前缀机。被检验每层捕获的序列因此具有亏损越来越大的前缀。

先构造通用前缀机 ​

枚举所有部分可计算函数的程序，并交错模拟每个程序在所有有限输入上的计算。对固定编号 $e$，每当观察到一个新停机输入 $p$，只在它与此前已接受的输入都无前缀关系时接受这次输入及其输出；重复事件忽略。检查只涉及有限个已接受输入，因而有效。

所得机器 $M_e$ 的定义域总前缀自由。如果原函数本来就是前缀机，过滤不会丢掉任何停机输入，因此 $(M_e)$ 仍包含所有前缀机。这是在枚举时保证性质，不需要判定任意程序是否具有该性质。

用前缀自由的编号标记 $1^{e}0$，定义

不同编号的标记互不为前缀；同一编号内则由 $M_e$ 的定义域保证前缀自由。于是 $U$ 是前缀机，并有 $K_U(\sigma )\le K_{M_e}(\sigma )+e+1$。对每个有限串，都存在只在一个指定程序上输出它的前缀机，所以 $U$ 的最短描述总存在。

Kraft–Chaitin：请求到来时就分配码字 ​

维护已分配程序集合 $A$ 和有限的空闲串集合 $F$，初始为 $A=\varnothing$、$F=\{\epsilon \}$。保持两个不变量：$A\cup F$ 的柱集两两不交且覆盖全部无限序列；$F$ 在每种长度上至多有一个串。

收到长度 $n$ 的请求时，在满足 $|z|\le n$ 的空闲串中选择最长的 $z$。分配

从 $F$ 删除 $z$，并加入沿这条零分支留下的兄弟节点

若 $|z|=n$，直接分配 $z$，不加入兄弟节点。这些新空闲柱集与 $[p]$ 恰好分割原来的 $[z]$，所以第一个不变量保持。因为选的是最长可用 $z$，此前不存在长度在 $|z|+1,\dots ,n$ 的空闲串，故第二个不变量也保持。

为何总找得到 $z$？分配当前请求之前，已用预算加上 $2^{-n}$ 至多为一，故空闲质量至少是 $2^{-n}$。若每个空闲串长度都大于 $n$，由于空闲集有限、每个长度至多一个，就有

矛盾。算法因此可逐项完成，不必预知未来请求，也不用把无限请求按长度排序。

机器 $M$ 在输入 $p$ 上模拟请求枚举与上述分配；一旦 $p$ 被分给请求 $(n,\sigma )$，就输出 $\sigma$，否则继续等待。这定义部分可计算函数，其停机域正是前缀自由的已分配程序集合。用通用性的同一个常数 $d_M$ 即得式 (1)。有限阶段前缀自由还保证无限极限中的任意两码字不冲突。

有效开集如何得到不可撤回的前缀自由枚举 ​

Levin–Schnorr 的反方向需要把有效开集 $V$ 写成

其中 $P$ 本身可以枚举且前缀自由。不能先输出较长串，再在较短前缀出现时撤回旧输出；前缀机已经分配的程序也不能这样反悔。

具体做法是维护当前已输出的有限前缀自由集合 $B$。原枚举器输出 $\tau$ 时，取 $L$ 为 $|\tau |$ 与 $B$ 中最大长度的最大值，若 $B$ 为空就取 $L=|\tau |$。枚举 $\tau$ 的所有长度 $L$ 延伸，仅输出那些没有 $B$ 中任何串作为前缀的延伸。

这些新柱集恰好组成 $[\tau ]$ 减去已经输出的并集；它们彼此不交，也与旧柱集不交。因此每一步保持相同的已覆盖开集，并且从不撤回输出。这个有限操作可计算，对带层号的枚举交错执行即可保持统一有效性。所有阶段输出的并集 $P$ 就是所求表示。[2]

Levin–Schnorr 的两个方向 ​

随机序列没有无界压缩亏损 ​

对每个整数 $c\ge 0$，定义

交错运行所有程序，观察停机输出，即可统一枚举这些开集；完全不必计算哪个程序最短。为了估计质量，在数学上为每个输出串 $\sigma$ 选一个最短程序 $p_{\sigma }$。不同输出对应不同程序，而这些程序都在 $U$ 的前缀自由定义域内，所以 Kraft 不等式及有限部分和的极限给出

对构成 $R_c$ 的串，$K(\sigma )\le |\sigma |-c$，故由柱集并集界

于是 $(R_c)$ 是合法 Martin-Löf 检验。若 $X$ 随机，它不在某层 $R_c$，所以每个前缀都满足 $K(X\upharpoonright n)>n-c$，从而满足式 (2)。此处选择最短程序只用于质量证明，没有把这种选择当成一个可执行步骤。

失败于有效检验会产生无界亏损 ​

反设 $X$ 非随机，有合法检验 $(V_m)$ 使 $X\in V_m$ 对每个 $m$ 成立。对每个 $k\ge 1$，用上面的不可撤回转换把 $V_{2k}$ 表示为前缀自由的统一可枚举集合 $P_k$。

每当 $\sigma$ 在第 $k$ 个集合被列出，就枚举一个请求

因为 $[\sigma ]\subseteq V_{2k}$，有 $2^{-|\sigma |}\le 2^{-2k}$，故 $|\sigma |\ge 2k$，请求长度确实非负。所有层放进同一个请求枚举器，总权重是

同一个串若在多个层出现，每次都计费；式 (4) 已经包括这些重复。Kraft–Chaitin 定理构造一台机器，通用性再给一个独立于 $k,\sigma$ 的常数 $d$，使每个请求满足

$X\in V_{2k}$ 保证有某个前缀 ${\sigma }_k\in P_k$。于是 $|{\sigma }_k|-K({\sigma }_k)\ge k-d$，随 $k$ 无界，违反式 (2)。这完成逆否证明，也闭合了两个方向。

乱序码长仍可在线分配 ​

依次请求 $(3,00),(3,01),(1,10),(2,11)$。总权重为 $1/8+1/8+1/2+1/4=1$；码长不是递增的。

程序 1 虽然到第三步才出现，先前一直为它保留着完整子树。若第一步任意选取空闲空间并打碎这棵子树，单有剩余总质量并不自动保证后续短码字可分配；每个长度至多一块空闲空间的不变量正避免这种碎片化。

再看开集枚举：原程序先输出 000，再输出 00。不可撤回转换先输出 000，第二次只补上 001，得到前缀自由集合 $\{000,001\}$，质量 $1/4$，其柱集并恰为 $[00]$。只删除旧串再写 00 虽可维护一个有限显示列表，却不能作为此前编码程序的枚举过程。

一个具体检验如何变成压缩请求 ​

令 $V_m=[0^m]$，则 $\mu (V_m)=2^{-m}$，并且 $0^{\mathrm{\infty }}$ 落在每一层。第 $2k$ 层只有串 $0^{2k}$，因此上面的构造请求长度为 $k$，输出为 $0^{2k}$。权重 $\sum _{k\ge 1}{2}^{-k}=1$，得到

它直接展示了非随机序列的无界亏损。这个界无需最优压缩：例如专门编码长度还可能更短，但当前构造已经足以否定式 (2)。

不能省略的约束 ​

前缀自由要求落在程序域。把它删掉，就不能对最短程序直接使用式 (3) 的 Kraft 总预算，因而不能把式 (2) 原样换成任意普通机器的最短输入长度。反方向也没有为每个可能前缀长度都申请一个短程序；请求来自每层的互不相交柱集表示，并且用稀疏层 $2k$ 使总预算可和。

定理是关于一条无限序列的全部前缀。单个长串恰好难压缩，或在有限测试中没有发现压缩方法，都没有验证这个无限量词。证明只构造停机事件的枚举，不提供总能认证 $K(\sigma )$ 精确值的程序。

若通用机改为 $U^{\prime }$，模拟关系双向给出 $|K_U(\sigma )-K_{U^{\prime }}(\sigma )|\le d$，所以常数亏损条件保持不变。序列的具体亏损常数依赖描述语言，随机序列这一集合则不依赖通用前缀机的选择。

开集检验与压缩描述给出同一随机性的两种入口：式 (3) 把短描述变成合法检验，式 (4) 把检验失败变成同一台机器中的一系列压缩见证。结合 Martin-Löf 随机序列具有测度一，可知满足统一亏损界的序列存在且几乎处处成立；这不是通过穷举计算最短程序来找出某条具体随机序列。