前缀复杂性
概述
前缀 Kolmogorov 复杂性 K_prefix(x) 要求合法程序集构成前缀码，修复了原始 Kolmogorov 复杂性的技术问题，使链式法则 K(x,y) = K(x) + K(y|x) + O(1) 精确成立。
关键内容
技术问题
Kolmogorov 的原始定义使用"普通"（非前缀）程序，导致链式法则 K(x,y) = K(x) + K(y|x) + O(1) 不能精确成立——存在 O(log K(x)) 的额外开销。
Levin 和 Chaitin 的修复
Levin (1974) 和 Chaitin (1975) 独立引入了前缀 Kolmogorov 复杂性：要求合法程序集构成前缀码（没有任何程序是另一个程序的前缀）。
关键性质
前缀复杂性满足完美的链式法则：
$$K(x,y) = K(x) + K(y|x) + O(1)$$
这使得 Kolmogorov 复杂性的代数性质与 Shannon 熵完美对应： - H(X,Y) = H(X) + H(Y|X) - K_prefix(x,y) = K_prefix(x) + K_prefix(y|x) + O(1)
与 Ω 常数的关系
$$\Omega = \sum_{p: U(p) \text{ halts}} 2^{-|p|}$$
Ω 是一个不可计算的超越数，其二进制展开的每一位都是算法随机的。
来源
- raw/books/信息论/09_kolmogorov_1965_three_approaches_to_information.md — Kolmogorov (1965) 深度解析