柯氏复杂性

历史与背景

算法信息论是计算机科学中的一个领域，研究柯氏复杂性和其他对于字符串（或者其他数据结构）的复杂性度量。
柯氏复杂性的理论和概念基于雷·所罗门诺夫的一些关键性理论。1960年，所罗门诺夫发表了《归纳推理的通用性理论导论》，作为他所创立的算法概率论的一部分。在1964年发表的《信息与控制》的第一和第二部分“归纳推理的正式理论” 中，他给出了一个更完整的描述。
安德雷·柯尔莫戈洛夫稍后于1965年在Problems Inform. Transmission 上独立发表了这一理论。格里高利·柴廷也在J. ACM 上发表了这一理论——柴廷的论文提交于1966年10月，于1968年12月修订，引用了所罗门诺夫和柯尔莫戈洛夫的论文。
这个理论认为，在所有从对字符串的描述中解码出字符串的算法里，存在一个最优的算法。这个算法对于所有的字符串来说，都可以得到和其他算法同样短的代码，除去一段固定的附加代码，这段代码不取决于字符串，只取决于所选择的算法。所罗门诺夫用这个算法和它所允许的代码长度，定义了一个字符串的“普适概率”universal probability，以对字符串行的归纳推断作为基础。柯尔莫哥诺夫利用这个理论定义了字符串的很多属性，包括复杂度、随机度和信息。
当柯尔莫戈洛夫了解到所罗门诺夫的工作之后，承认了所罗门诺夫的发现在先。在很长一段时间内，所罗门诺夫的工作在苏联比在西方更为人知晓。科学界的共识一般是把和复杂度有关的工作归功于柯尔莫戈洛夫，因为他主要研究串行的随机程度；而算法信息论的工作则归功于所罗门诺夫，他主要集中研究用普适概率分布来进行串行预测。这两个领域的边界，包括描述复杂度和概率通常被称为柯尔莫戈洛夫复杂度。计算机科学家李明认为这是马太效应的体现。
柯尔莫戈洛夫复杂度或者算法信息论有很多变体，其中一个广泛应用的概念是“自生成程序”self-delimiting-program，主要来自于里奥尼德·列文（1974）。
Mark Burgin基于布鲁姆公理（Blum 1967），对于柯氏复杂度进行了公理化（Burgin 1982）。

柯氏复杂性的不可计算性

定理：存在字符串，拥有任意大的柯氏复杂度。严格表述为：对于任意n ∈ ℕ，存在一个字符串s 的复杂度K(s) ≥ n
证明：反证。如果定理不成立，则任意的无限长字符串，都可以使用有限个数，复杂性小于n 比特的程序 来生成了。
定理： K 不是一个可计算函数。也就是说，不存在一个程序，可以把字符串s 作为输入，然后输出它的K(s)。
证明：以下的反证法将使用类似Pascal语言的代码。为了证明的简单起见，该语言的描述（即其解释器）大概有1,400,000 比特。下面开始反证法，假设有这样一个程序存在：
  function KolmogorovComplexity(string s)
它可以把字符串s 作为输入，然后输出它的K(s)；简单起见，假设这一函数的长度是7,000,000,000 比特。现在考虑另一段长度为1,288 比特的程序：
  function GenerateComplexString()
     for i = 1 to infinity:
        for each string s of length exactly i
           if KolmogorovComplexity(s) >= 8000000000
              return s
它将KolmogorovComplexity 作为子程序，这个程序会从短到长检查所有的字符串，直到找到一个复杂度至少有8,000,000,000 比特的字符串s 。这也就意味着，任何短于8,000,000,000 比特的程序都不可能输出这个字符串。但是，以上的整个程序能够输出s ，而其长度却只有7,001,401,288 比特，反证完毕。（如果 KolmogorovComplexity 的代码要更短一些，反证依然成立。如果它要更长，那么 GenerateComplexString 中使用的常数也可以相应变大。）
以上使用的反证法类似于佩里悖论：“₁不 ₂能 ₃用 ₄少 ₅于 ₆二 ₇十 ₈个 ₉字 ₁₀定 ₁₁义 ₁₂的 ₁₃最 ₁₄小 ₁₅整 ₁₆数”。也可以使用停机问题H 的不可计算性来推导K 的不可计算性，因为 K 和 H 是图灵等价的。
它的一个结论，在程序员群体中被幽默地称为充分就业定理，其涵义之一是指不存在一个最优的规模优选编译器。