柯氏复杂性

在计算机科学中，一个对象比如一段文字的柯氏复杂性（柯尔莫哥洛夫复杂性, 描述复杂性, Kolmogorov-Chaitin complexity, stochastic complexity, 算法熵）是衡量描述这个对象所需要的信息量的一个尺度。 以下面的两个长度为64的字符串为例。

0101010101010101010101010101010101010101010101010101010101010101

1100100001100001110111101110110011111010010000100101011110010110

第一个字符串可以用中文简短地描述为“重复32个‘01’”。第二个字符串没有明显的简短描述。

一个字符串$s$的柯氏复杂性（$C(s)$或者$K(s)$，区别如后）是这个字符串的最短描述的长度。换言之，一个字符串$s$的柯氏复杂性是能够输出且仅输出这个字符串的最短计算机／图灵机程序的长度。 这样的定义导致在使用不同的描述语言或者不同的图灵机的时候柯氏复杂性不一样。所以在讨论柯氏复杂性的时候，通常都事先固定一个通用图灵机$U$作为参照。可以证明在使用$U$做参照的时候，对任意的图灵机$M$，都存在一个仅决定于$U$和$M$的常数$c_M$使得对所有的字符串$s$相对于$U$的柯氏复杂性$C_U$（或者$K_U$）和相对于$M$的柯氏复杂性$C_M$（或者$K_M$）都满足

$C_U(s)\leq C_M(s)+c_M$。

根据这点，通常确定了一个参照图灵机后就用$C$和$K$表示柯氏复杂性（省略$U$）。

参考资料

• 李明，[荷]P.M.B.威塔涅（Paul Vitanyi），描述复杂性，科学出版社，北京，1998
• Ming Li and Paul Vitanyi, An Introduction to Kolmogorov Complexity and Its Applications, 2nd Edition, Springer Verlag, 1997