从“程序长度”到“对称性”：一篇 CAS 论文给编码定理换了几何语言

导语

经典算法信息论关心一个对象“有多难描述”：如果一个二进制字符串能由很短的程序生成，它通常被认为更简单；如果只能靠冗长描述才能指定，它就更复杂。arXiv 论文《CAS I: A Geometric Coding Theorem》试图从另一个角度重述这个问题：不要先问“生成它的程序有多短”，而是问“在一个对称性系统中，它有多容易被单独固定下来”。

这篇论文是 Computational Algorithmic Statistics（CAS）系列的第一篇，目标是把算法信息论与群论语言连接起来。作者考虑二进制字符串集合上的可计算双射，并把这些变换称为“对称性”。在这个设定中，一个字符串的复杂度不再只由生成程序衡量，还可以由它在对称群中的几何位置来刻画。

核心要点

• 对称性作为可计算双射：论文将作用在二进制字符串集合上的可计算一一映射视为对称性。这使得字符串不只是孤立对象，而是处在一组可计算变换构成的结构之中。

• “对称先验”定义复杂度信号：作者定义了一个字符串的 symmetry prior，即从给定群中随机选择一个对称性时，该对称性把该字符串作为唯一不动点的概率。直观地说，如果某个字符串经常能被对称性“单独留下”，它就在该群结构下具有较高的先验权重。

• 几何版编码定理：论文证明，对于所谓 fix-retractable 的对称群，也就是存在可计算截面、能为每个字符串选择一个隔离对称性的群，对称先验是通用下半可计算半测度。在这一条件下，经典编码定理获得了一个群论/几何意义上的对应版本。

• Galois 连接与闭点结构：除编码定理外，论文还建立了子群与二进制字符串子集之间的 Galois 连接，用以刻画闭点、极大闭子群，并进一步讨论稠密子群形成的 join-semilattice 结构。

意义与影响

这项工作的重要性主要不在于立即给出现成 AI 系统的工程改进，而在于提供一种新的理论坐标系。经典编码定理把概率、复杂度与最短描述联系起来；这篇论文则尝试说明，当我们把对象放入可计算对称群中，也能得到类似的普适复杂度度量。

这对算法统计、信息论以及形式化复杂度研究都有启发意义。它可能帮助研究者从“对象如何被生成”转向“对象如何被变换结构识别”，进而讨论数据模式、模型归纳偏置或结构性表示的复杂度。当然，当前论文仍是高度理论化的第一步，摘要中没有给出实验或应用系统，读者应将其视为一个数学框架的奠基，而非面向产品的技术发布。

来源：arXiv