柯氏复杂性

维基百科,自由的百科全书
跳转至: 导航搜索

算法信息论计算机科学数学的一个分支)中,一个对象比如一段文字的柯氏复杂性柯尔莫哥洛夫复杂性, 描述复杂性, 柯尔莫哥洛夫-柴定英语Gregory Chaitin复杂度, 随机复杂度, 算法熵)是衡量描述这个对象所需要的信息量的一个尺度。 安德雷·柯尔莫哥洛夫于1963年发现了它,因此以他的名字命名。[1][2]

以下面的两个长度为64的字符串为例。

0101010101010101010101010101010101010101010101010101010101010101
1100100001100001110111101110110011111010010000100101011110010110

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

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

C_U(s)\leq C_M(s)+c_M。根据这点,通常确定了一个参照图灵机后就用CK表示柯氏复杂性(省略U)。

不难证明,任何字符串的柯氏复杂度都不会比字符串自身的长度超过太多。类似与上文中的0101字符串,它的柯氏复杂度和字符串的长度关系不大,因此并不复杂。

柯氏复杂度的概念可以用于定义和证明康托尔的对角论证法哥德尔不完备定理、图灵的停机问题

定义[编辑]

柯氏复杂度可以适用于任何数学概念,但是本文只针对字符串。首先需要确定我们用以描述字符串的语言,它可以基于任何计算机语言,例如LISPPascalJava虚拟机。如果 P 是一个可以输出字符串 x的程序,则 Px的描述。描述长度就等于程序 P 作为字符串的长度,乘上每个字符的比特数。(例如,对于 ASCII来说是7)

参考资料[编辑]

  1. ^ Kolmogorov, Andrey. On Tables of Random Numbers. Sankhyā Ser. A. 1963, 25: 369–375. MR 178484. 
  2. ^ Kolmogorov, Andrey. On Tables of Random Numbers. Theoretical Computer Science. 1998, 207 (2): 387–395. doi:10.1016/S0304-3975(98)00075-9. MR 1643414.