本系列参考的内容主要来自教材《An Introduction to Kolmogorov Complexity and Its Applications》, 外加ai的辅助阅读, 旨在介绍柯尔莫哥洛夫复杂度(Kolmogorov Complexity)的含义, 数学细节, 以及相关应用. 感谢Gemini, 以及其它ai还有我某些不愿意透露姓名的朋友帮助. 什么是Kolmogorov Complexity(KC)？ 在给出概念的定义, 我们先来看几个例子. 考虑二进制字符串: $$ 00000000000000000000000000,\\ 01000110110000010100111001,\\ 10010011011000111011010000 $$从概率上来看, 这三个字符串产生的概率是相同的, 均为 $2^{-26}$ , 但从人类直观出发, 会觉得第一个字符串更规律. 如果你的注意力不那么涣散的话, 还能留意到第二个序列由$0,1,00,01,10,11,000,...$生成, 而第三个序列是真实的抛一枚硬币所产生的. 从传统概率论的角度来看, 这三者生成的概率是一样的, 但从直觉出发, 前两个序列更加的简单. 而实际上这种直觉也并不是错觉, 在python语言中, 对于第一个式子, 我们有: print("0"*26) 但对于剩下两个式子, 我们大概率很难将其缩减为像上面这个式子这么简短的形式. 因此, 我们可以粗略用生成一个字符串程序长度来衡量这个字符串的随机性. 显然, 一个字符串存在着很多种生成办法, 为便于比较, 我们不严谨地定义: 在给定描述方法U下, 生成一段字符串x的最短描述长度称为这个字符串的柯尔莫哥洛夫复杂度(Kolmogorov Complexity), 记为$K_U(x)$ 描述方法严格定义实际上需要是一个通用图灵机, 而且必须是无前缀的(设 $P$ 是图灵机 $M$ 所有能使其停机的输入字符串（程序）的集合。如果对于 $P$ 中的任意两个不同的字符串 $p_1$ 和 $p_2$，$p_1$ 都不是 $p_2$ 的前缀，那么图灵机 $M$ 就被称为无前缀图灵机。). ...