Connections in Math: the two kinds of random
7 days ago
- #Algorithmic Information Theory
- #Kolmogorov Complexity
- #Shannon Entropy
- 这个谜题对比了两份统计特征完全相同的百万位数字文件：一份是随机噪声；另一份是π的前一百万位数字。
- 两份文件都具有均匀的数字频率分布，使它们无法通过统计测试区分，并拥有最大的香农熵——意味着没有统计冗余可用于压缩。
- 然而，π可以通过一个计算它的简短程序进行显著压缩，而随机文件由于缺乏简单的生成规则无法被压缩。
- 香农熵根据信源中符号频率来衡量可压缩性，而柯尔莫哥洛夫复杂度则测量输出特定字符串的最短程序长度，捕捉结构性压缩的可能性。
- π展现了最大熵但最小柯尔莫哥洛夫复杂度的特例，突显了统计随机性与算法随机性之间的区别。
- 计数论证表明大多数字符串都是不可压缩的（即它们的最短描述几乎与自身等长），但不可能精确定位具体的不可压缩字符串。
- 柯尔莫哥洛夫复杂度是不可计算的：我们可以通过发现短程序找到上界，但由于停机问题和贝里悖论，无法确定性地建立下界。
- 两种压缩类型最终都关联到区分成本——从众多可能性中选择一个特定项——香农熵将此成本平均化，而柯尔莫哥洛夫复杂度将其应用于个体对象。
- 发现可压缩性（可能）与证明不可压缩性（不可能）之间的不对称性，反映了计算和证明领域更深层的局限性。