Berry悖论
概述
Berry 悖论（1906）是"最小的不能用二十个英文单词定义的正整数"——这个描述本身只用了不到二十个词。Chaitin 将其形式化为 Kolmogorov 复杂性不可计算性的证明。
关键内容
原始悖论
"The smallest positive integer not definable in under twenty English words."
这个短语本身只用了 14 个英文单词，却定义了一个"不能用少于 20 个单词定义的数"——自相矛盾。
Chaitin 的形式化
Chaitin 将 Berry 悖论转化为严格的数学定理：
假设存在程序 P 能计算 Kolmogorov 复杂性 I(x)。构造程序 Q： - 枚举所有字符串 x，对每个计算 I(x) - 输出第一个满足 I(x) ≥ N 的 x
Q 的长度约 |P| + log N，但它输出了一个"复杂度应该 ≥ N"的字符串。当 N 足够大时，|P| + log N < N——矛盾！
意义
Berry 悖论不是逻辑的 bug，而是 feature——它揭示了形式系统的信息论极限：一个复杂性有限的形式系统不能证明某个字符串具有超过系统自身复杂性的复杂性。
与 Gödel 不完备定理的关系
Chaitin 用 Berry 悖论的形式化给出了 Gödel 不完备定理的信息论版本： - Gödel 版：存在真但不可证的命题（源于自指与对角化） - Chaitin 版：存在复杂但无法被证明复杂的字符串（源于公理系统的信息量有限）
来源
- raw/books/信息论/10_chaitin_1966_length_of_programs.md — Chaitin (1966) 深度解析