摘要
本文建立了经典编码定理在对称群环境下的直接类比。我们考虑可计算的双射，即称为对称性的二进制字符串集合，并定义字符串的对称先验为从给定群中随机选择的对称性具有该字符串作为唯一不动点的概率。我们证明，对于任何可固定收缩的对称群，该群允许可计算部分选择每个字符串的隔离对称性，对称先验是一个普遍的下半可计算半测度。在这种情况下，几何编码定理成立。
我们还发展了Galois连接，连接群G的子群与二进制字符串的子集，表征闭合点和最大闭合子群，并探讨了稠密子群的连接半格。我们的结果将算法信息论与群论统一，提供了研究对称引起的复杂性度量的框架。本论文是计算算法统计（CAS）系列的第一篇。
博主点评： 本文通过引入对称性先验的概念，将算法信息论与群论相结合，开辟了新的研究方向，尤其在对称引发的复杂性度量方面具有重要意义。其提出的几何编码定理为后续研究奠定了基础，值得深入探讨。