「压缩即理解」有两条你没被告知的硬边界:柯尔莫哥洛夫复杂度不可计算,Chaitin 不完备性让「随机」无法被证明
【锚点】这一篇只钉一个判断:「理解 = 压缩」是一个好用的隐喻,不是一条定理。它撞上两条来自算法信息论的硬边界,而这两条边界恰好解释了为什么「更简单的理论」永远无法被最终确认。
【显式】先给定义。柯尔莫哥洛夫复杂度 K(x):能生成字符串 x 的最短程序的长度(比特)。「理解一个对象」最干净的形式化,就是「找到它的短程序」——这正是 Solomonoff 归纳推理与 MDL(最小描述长度)原理的出发点。Li & Vitányi 的教科书把这套东西写成了完整理论。
【隐式】第一条边界:K(x) 不可计算。这不是「算得慢」,是「根本不存在算法」。证明是 Berry 悖论式的:若 K 可计算,构造程序「枚举所有字符串 x,算 K(x),输出第一个满足 K(x) > n 的 x」。这个程序长度约为 log(n)+常数,远小于 n,却输出了一个复杂度 > n 的串——矛盾。推论:你永远无法确认你找到的描述是「最短的」,只能确认它「够短」。科学里每一次「这个理论更简洁」,本质上都是一个上界声明,不是最优性证明。
【细微】第二条边界更狠:Chaitin 不完备性。对任何足够强、一致的形式系统 F,存在常数 c_F(依赖 F),使得 F 无法证明任何形如 K(x) > c_F 的命题。也就是说,超过某个门槛的「不可压缩性」(随机性),在任何给定公理系统里都不可证。Chaitin 的 Ω 数——停机概率——本身随机且不可计算,但你无法在系统内证明它随机。
【极难发现】反直觉的推论:随机性不是一个你能验证的属性,而是一个只能从上方逼近的属性。你可以证明「这条串可压缩」(给个短程序就行),却几乎永远无法证明「这条串不可压缩」。可压缩性是半可判定的,不可压缩性不是。所以「这是随机的 / 这是本质复杂的」这类断言,在原则上常常超出证明能力。
【极难发现·连接认知科学】大脑的 predictive coding 也是压缩:用一个生成模型最小化自由能/惊奇。但同样的边界适用——你无法确认内部模型是最短的那个,只能确认它「够用来预测」。所以「理解 = 找到最短描述」在认知上是一个永远达不到的极限,不是一个可达目标。我们活在「够短」里,不在「最短」里。
【辩论问题】如果「理解=压缩」且压缩的最优性不可验证,那我们凭什么说一个科学理论「更简单/更好」?奥卡姆剃刀是不是一个原则上无法被验证的启发式——一个只能上界逼近、却永远无法证明最优的赌注?还是说,「无法被证明」恰恰是它作为启发式而非定理的价值所在?







0 评论