柯氏复杂性

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

算法信息论计算机科学数学的一个分支)中,一个对象比如一段文字的柯氏复杂性柯尔莫哥洛夫复杂性, 描述复杂性, 柯尔莫哥洛夫-柴定英语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)

我们也可以使用图灵机的编码。每一个图灵机 M 都对应一个字符串 <M>。如果 M 是一个图灵机,给它输入字符串 w 它会输出字符串 x,那么这段拼合起来的字符串 <M> w 就是 x的描述。这种描述更适合比较严谨的证明,通常是在正式研究中才会使用。在本文的讨论中会使用比较非正式的描述。

对于任何一个字符串 s ,都存在至少一个描述。可以用以下程序表示:

 function GenerateFixedString()
    return s

如果 s 的描述 d(s) 长度达到最小(也即是使用最少的比特数),它就可以称为 s 的“最小描述”。同时,d(s)的长度(也就是这个描述使用的比特数)就是 s的“柯氏复杂度”,写作 K(s)。可以表示为:

K(s) = |d(s)|.

最小描述长度取决于选择什么语言来描述;但是改变描述语言所带来的长度变化是有限的。(这个属性称作不变性理论(invariance theorem))

不变性理论[编辑]

非正式表述[编辑]

一些描述语言可以被称作“最优的”(optimal)。它们有如下属性:如果我们用任意一个描述语言来一个对象,我们也可以用最优的描述语言来描述那个对象,只需要在原来的那段描述前面加上一段固定的前缀。这段前缀仅仅取决于使用哪一种描述语言,不取决于对对象的描述,也不取决于被描述的对象。

以下是“最优描述语言”(Optimal description language)的一个例子。这个语言中的描述都会包括以下两部分:

  • 第一部分,描述了某一种描述语言。
  • 第二部分是,使用那一种描述语言来描述对象。

更技术性的说法是,第一部分是一段计算机程序,如果把第二部分输入这个程序,就会输出该对象。

不变性理论指的是:对于任意的描述语言 L,最优描述语言都至少和 L 同样有效,但是会增加一段固定的前缀。

证明: L 中任意的一段描述 D ,都可以转换成为最优描述语言中的一段描述,这段描述包括将 L 描述为一段计算机程序 P (前面提到的第一部分),然后将原来的描述 D 作为这段程序的输入(第二部分)。新的描述 D ’ 的长度(近似值)为:

|D’| = |P| + |D|

P 的长度为常数,不取决于 D ,所以,至多有一个固定长度的前缀,不取决于描述对象。所以,最优描述语言在up to固定前缀的意义上是通用的。

更正式的描述[编辑]

"'定理"':设 K1K2 是满足 图灵完备性的描述语言 L1L2的复杂度函数,则存在一个常数 c ,仅取决于对于语言 L1L2 的选择,有:

s. -cK1(s) - K2(s) ≤ c.

证明:根据对称性,可以证明存在一个常数 c 对于所有的字符串 s 满足:

K1(s) ≤ K2(s) + c.

然后,假设语言 L1 中存在一个程序,相当于是 L2解释器:

  function InterpretLanguage(string p)

其中 pL2 中的一个程序。解释器有以下属性:

运行 InterpretLanguage ,输入 p 将会返回运行 p 的结果。

然后,设 L2 中的程序 Ps 的最小描述,则 InterpretLanguage(P) 将会返回字符串 s。而 s 的描述长度,是以下两项之和:

  1. 程序 InterpretLanguage 的长度,可以看做常数 c
  2. P 的长度。根据定义,就是 K2(s).

以上证明了所需的上界。

历史与背景[编辑]

算法信息论是计算机科学中的一个领域,研究柯氏复杂性和其他对于字符串(或者其他数据结构)的复杂性度量。

柯氏复杂性的理论和概念基于雷·所罗门诺夫英语Ray Solomonoff的一些关键性理论。1960年,所罗门诺夫发表了《归纳推理的通用性理论导论》[3],作为他所创立的算法概率论英语Algorithmic probalility的一部分。在1964年发表的《信息与控制》的第一和第二部分 “归纳推理的正式理论” 中,他给出了一个更完整的描述。[4][5]

安德雷·柯尔莫戈洛夫稍后于1965年在 Problems Inform. Transmission[6] 上独立发表了这一理论。乔治·柴定也在 J. ACM 上发表了这一理论——柴定的论文提交于1966年10月,于1968年12月修订,引用了所罗门诺夫和柯尔莫戈洛夫的论文。[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. 
  3. ^ Solomonoff, Ray. A Preliminary Report on a General Theory of Inductive Inference (PDF). Report V-131 (Cambridge, Ma.: Zator Co.). February 4, 1960.  revision, Nov., 1960.
  4. ^ 编辑
  5. ^ 编辑
  6. ^ Kolmogorov, A.N. Three Approaches to the Quantitative Definition of Information. Problems Inform. Transmission. 1965, 1 (1): 1–7. 
  7. ^ 编辑