捡起搁置一旁的谜题

2026 年 7 月 2 日探讨数学领域问题，上一篇文章结尾留谜题，现再拿出。想象两个各含一百万个数字的文件，一为纯粹噪声如掷百万次十面骰子记录结果，二是 π 的前一百万个数字。从统计学家视角统计数字频率，两文件各数字出现次数约为总数十分之一，直方图几乎一样，经随机测试都通过，统计指标看两文件相同，似无法压缩随机数据。但一个能用三行代码“计算 π，打印一百万个数字”发给对方精确重现，另一个只能逐位发送。核心问题是统计相同为何压缩性不同，答案需明确“可压缩性”含义，其包含两种概念，有一种可压缩性存在时能确认，不存在时无法排除。

两种压缩方式

文章讨论无损压缩，即不丢信息、不近似处理，给简短描述能精确重建原始数据。事物可压缩有两个原因，一是统计性，常见符号分配短编码、罕见符号分配长编码可节省空间，如 zip 文件和霍夫曼编码；二与生成过程有关，即使符号分布均匀，来自简单规则的事物也可压缩，因简短性体现在生成过程而非符号频率。文章探讨统计冗余是否是唯一可压缩性形式，π 给出否定答案。

统计性压缩：熵

从预算的角度构建熵的概念

讨论 π 前需明确“统计压缩”衡量指标是熵。熵是符号源平均“意外程度”，符号源总发相同符号熵为零，等概率发十个不同数字熵最大，多数符号源处于两者间，熵是各情况按符号频率加权平均值。熵与压缩联系直接，意外程度用比特表示，可预测内容可省略，意外内容需传输，符号源熵是最短平均消息长度、无损编码下限。借鉴 Chris Olah《可视化信息理论》思路推导公式，给符号分配码字，出现概率为 p 的符号，理想码字长度是 log₂(1/p) 比特，常见符号码字短，罕见符号长。可将平均消息长度看作面积，香农熵是最小可能面积、最短平均消息长度。log₂(1/p) 也是确定占据 p 比例可能性事物所需“是/否”问题数量。如四个符号概率分别为 1/2、1/4、1/8、1/8，理想长度 1、2、3、3，可构建无前缀冲突码字，平均长度 1.75 比特等于 H。十个数字均匀分布时熵最大为 log₂10 ≈ 3.32 比特，两文件熵达最大，统计上不可压缩。

熵的盲点

熵是符号源属性，非单个固定序列属性，严格无“π 的熵”说法。“测量”文件熵是统计数字频率当作符号源概率计算熵，用频率概括序列会忽略顺序，有相同数字频率的序列看似相同，π 和噪声文件虽频率相同，但 π 由简单规则生成。并非所有统计方法都无视规则，知道正确符号源可描述 π 生成过程使其熵变小。需针对单个对象、无需符号源的度量，即柯尔莫哥洛夫复杂度。

基于生成过程的压缩：柯尔莫哥洛夫复杂度

字符串的柯尔莫哥洛夫复杂度 K(x) 是输出该字符串的最短程序长度。由十亿个零组成的字符串复杂度低，真正随机长度为 n 的字符串复杂度约为 n，π 复杂度低，几百比特的小程序可计算其数字。谜题解决是因用了两种衡量标准，香农熵基于统计，关注整体集合、只看频率；柯尔莫哥洛夫复杂度基于结构，关注单个对象、能看到规则和生成过程。π 是两者差异最大例子，熵最大、复杂度最小，统计看“随机无法压缩”，复杂度看“简单五行程序可生成”。对真正随机符号源，输出的预期柯尔莫哥洛夫复杂度等于香农熵，误差在小常数范围内，整体分布平均情况两者一致，统计学是算法结构关注整体集合时的影子，只有隐藏生成规则的单个特殊对象两者有分歧，π 是极端代表，多数对象无特别之处。

几乎没有东西可以被压缩

论断“几乎每个字符串的最短描述就是它本身，大多东西无法压缩”。固定长度 n，长度为 n 的字符串有 2^n 个，长度小于 n 的描述有 2^n - 1 个，至少有一个长度为 n 的字符串无更短描述。若要描述比原字符串短 c 比特，长度为 n - c 的描述约 2^(n - c) 个，最多 2^(-c) 比例的字符串可压缩 c 比特，深度压缩罕见且要求压缩程度越高越罕见。证明不可压缩字符串占多数但未指出具体字符串，像数门和钥匙，知道有门打不开但不知是哪扇。程序本身是字符串，可将字符串和程序数量比较相减。若不存字符串本身，存索引或种子等方案都会失败，因从大小为 N 的集合选特定事物需 log₂N 比特名称。π 生成器只产生一个输出无需选择，随机字符串需精确选出一个要付出全部 log₂(2^n) = n 比特。目前内容可通过简单计数证明，找最短描述时情况变复杂。

难题：无法计算

柯尔莫哥洛夫复杂度定义简单但无法实际计算，无算法输入字符串输出复杂度。原因是不对称性，可找短程序证明复杂度上限，如找到长度 50 的程序能打印字符串，可证明 K(x) 最多为 50 且可继续找更短程序降低上限；但证明复杂度下限难，证明 K(x) 至少为 50 需排除所有更短程序，程序可能运行很久才出结果或永远运行，无法确定。上限可找，下限无法确定，能发现事物更具可压缩性但无法证明和看起来一样不可压缩。还有更严格结论，K 无法计算源于贝里悖论，假设能计算 K，可写短程序打印复杂度大于十亿的字符串，这使字符串有几千比特描述和十亿比特复杂度，矛盾，所以 K 不可计算。论证靠自我指涉，因程序是字符串，其他程序可操作它，此事实在计数论证中也发挥作用。

本质探讨

文章核心是两种陈述区别，“有 N 个事物”是关于集合大小陈述，不区分事物，信息廉价；“这是第 K 个事物”是挑出特定事物陈述，需 log₂N 比特区分。多数问题源于此差距，“大多数字符串不可压缩”是计数陈述易证明，“这个字符串不可压缩”是点名陈述无法做到。寻找和排除不对称性中也体现此问题，找到短程序是有限任务，排除所有更短程序是无限集合断言。信息是区分事物代价，熵是此代价在分布上的平均值，柯尔莫哥洛夫复杂度是针对特定对象的代价，两者问同样问题“在多少个事物中，是哪一个”。压缩是无需选择部分，π 几乎可压缩到零，随机字符串无法压缩，统计性和结构性压缩归结为区分代价，最廉价陈述是不区分事物的“有 N 个事物”。

后续展望

文章围绕为何能压缩 π 却不能压缩其统计“双胞胎”问题展开，后续想在几方面深入探讨。当压缩变成学习，有损压缩概念是生成与数据近似的最短程序，保留结构丢弃噪声，这是学习本质，奥卡姆剃刀成计算，最优解释是拟合数据的最短程序。当无法证明时，计数论证未指出具体不可压缩字符串，此问题涉及证明本身极限，形式系统无法证明特定字符串复杂，与哥德尔理论有关。有限的宇宙中，若只能命名物理事物且宇宙状态有限，压缩故事类似热力学熵故事，热力学第二定律可能是计数论证在时间中的体现。但这些留待以后文章讨论，本文能证明 π 可压缩，无法确定其“双胞胎”不可压缩，有短描述能找到，无法证明不存在短描述。

- [ #信息论 ](/tags/information - theory)

- [ #柯尔莫哥洛夫复杂度 ](/tags/kolmogorov - complexity)

- [ #熵 ](/tags/entropy)

- [ #从头开始 ](/tags/from - scratch)

新文章直接发送到收件箱，包括文章、项目和数学推导，无垃圾邮件，随时可取消订阅。

订阅

感谢订阅，请查看收件箱进行确认。