柯氏複雜性

在算法信息論（計算機科學和數學的一個分支）中，一個對象比如一段文字的柯氏複雜性（亦作柯爾莫哥洛夫複雜性、描述複雜性、柯爾莫哥洛夫-柴廷複雜度、隨機複雜度，或算法熵）是衡量描述這個對象所需要的信息量的一個尺度。柯氏複雜性是由安德雷·柯爾莫哥洛夫於1963年發現，所以用他的名字命名。

以下面的兩個長度為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$）。

不難證明，任何字符串的柯氏複雜度都不會比字符串自身的長度超過太多。類似與上文中的0101字符串，它的柯氏複雜度和字符串的長度關係不大，因此並不複雜。

與康托爾的對角論證法、哥德爾不完備定理和圖靈的停機問題類似，柯氏複雜度的概念可以用於闡述和證明不可能性。

定義

柯氏複雜度可以適用於任何數學概念，但是本文只針對字符串。首先需要確定我們用以描述字符串的語言，它可以基於任何計算機語言，例如LISP、Pascal或Java字節碼。如果 P 是一個可以輸出字符串 x的程序，則 P 是 x的描述。描述長度就等於程序 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，D 都可以轉換成為最優描述語言下的一段描述，這段描述包括將 L 描述為一段計算機程序 P （前面提到的第一部分），然後將原來的描述 D 作為這段程序的輸入（第二部分）。新的描述 D 』 的長度（近似值）為：

|D』| = |P| + |D|

P 的長度為常數，不取決於 D ，所以，至多有一個常數項長度的前綴，不取決於描述對象。所以，最優描述語言在up to固定前綴的意義上是通用的。

更正式的描述

"'定理"'：設 K₁ 和 K₂ 是滿足 圖靈完備性的描述語言 L₁ 和 L₂的複雜度函數，則存在一個常數 c ，僅取決於對於語言 L₁ 和 L₂ 的選擇，有：

∀s. -c ≤ K₁(s) - K₂(s) ≤ c.

證明：根據對稱性，可以證明存在一個常數 c 對於所有的字符串 s 滿足：

K₁(s) ≤ K₂(s) + c.

然後，假設語言 L₁ 中存在一個程序，相當於是 L₂ 的解釋器:

  function InterpretLanguage(string p)

其中 p 是 L₂ 中的一個程序。解釋器有以下屬性：

運行 InterpretLanguage ，輸入 p 將會返回運行 p 的結果。

然後，設 L₂ 中的程序 P 是 s 的最小描述，則 InterpretLanguage(P) 將會返回字符串 s。而 s 的描述長度，是以下兩項之和：

1. 程序 InterpretLanguage 的長度，可以看做常數 c。
2. P 的長度。根據定義，就是 K₂(s).

以上證明了所需的上界。

歷史與背景

算法信息論是計算機科學中的一個領域，研究柯氏複雜性和其他對於字符串（或者其他數據結構）的複雜性度量。

柯氏複雜性的理論和概念基於雷·所羅門諾夫的一些關鍵性理論。1960年，所羅門諾夫發表了《歸納推理的通用性理論導論》，作為他所創立的算法概率論的一部分。在1964年發表的《信息與控制》的第一和第二部分 「歸納推理的正式理論」 中，他給出了一個更完整的描述。

安德雷·柯爾莫戈洛夫稍後於1965年在 Problems Inform. Transmission 上獨立發表了這一理論。格里高利·柴廷也在 J. ACM 上發表了這一理論——柴廷的論文提交於1966年10月，於1968年12月修訂，引用了所羅門諾夫和柯爾莫戈洛夫的論文。

這個理論認為，在所有從對字符串的描述中解碼出字符串的算法裡，存在一個最優的算法。這個算法對於所有的字符串來說，都可以得到和其他算法同樣短的代碼，除去一段固定的附加代碼，這段代碼不取決於字符串，只取決於所選擇的算法。所羅門諾夫用這個算法和它所允許的代碼長度，定義了一個字符串的「普適概率」universal probability，以對字符序列的歸納推斷作為基礎。柯爾莫哥諾夫利用這個理論定義了字符串的很多屬性，包括複雜度、隨機度和信息。

當柯爾莫戈洛夫了解到所羅門諾夫的工作之後，承認了所羅門諾夫的發現在先。在很長一段時間內，所羅門諾夫的工作在蘇聯比在西方更為人知曉。科學界的共識一般是把和複雜度有關的工作歸功於柯爾莫戈洛夫，因為他主要研究序列的隨機程度；而算法信息論的工作則歸功於所羅門諾夫，他主要集中研究用普適概率分布來進行序列預測。這兩個領域的邊界，包括描述複雜度和概率通常被稱為柯爾莫戈洛夫複雜度。計算機科學家李明認為這是馬太效應的體現。

柯爾莫戈洛夫複雜度或者算法信息論有很多變體，其中一個廣泛應用的概念是「自生成程序」self-delimiting-program，主要來自於里奧尼德·列文（1974）。

Mark Burgin基於布盧姆公理（Blum 1967），對於柯氏複雜度進行了公理化（Burgin 1982）。

基本結論

在以下討論中，我們用 K(s) 來表示字符串 s 的複雜度。

顯而易見，一個字符串的最小描述不可能超過字符串本身的長度太多。上文中的程序GenerateFixedString 可以輸出 s ，長度比 s 稍長。

定理：存在一個常數 c ，使得：

∀s. K(s) ≤ |s| + c

柯氏複雜性的不可計算性

定理：存在字符串，擁有任意大的柯氏複雜度。嚴格表述為：對於任意 n ∈ ℕ，存在一個字符串 s 的複雜度 K(s) ≥ n

證明：反證。如果定理不成立，則任意的無限長字符串，都可以使用有限個數，複雜性小於 n 比特的程序 來生成了。

定理： K 不是一個可計算函數。也就是說，不存在一個程序，可以把字符串 s 作為輸入，然後輸出它的 K(s)。

證明：以下的反證法將使用類似Pascal語言的代碼。為了證明的簡單起見，該語言的描述（即其解釋器）大概有 7006140000000000000♠1400000 比特。下面開始反證法，假設有這樣一個程序存在：

  function KolmogorovComplexity(string s)

它可以把字符串 s 作為輸入，然後輸出它的 K(s)；簡單起見，假設這一函數的長度是 7009700000000000000♠7000000000 比特。現在考慮另一段長度為 7003128800000000000♠1288 比特的程序：

  function GenerateComplexString()
     for i = 1 to infinity:
        for each string s of length exactly i
           if KolmogorovComplexity(s) >= 8000000000
              return s

它將 KolmogorovComplexity 作為子程序，這個程序會從短到長檢查所有的字符串，直到找到一個複雜度至少有 7009800000000000000♠8000000000 比特的字符串 s 。這也就意味着，任何短於 7009800000000000000♠8000000000 比特的程序都不可能輸出這個字符串。但是，以上的整個程序能夠輸出 s ，而其長度卻只有7009700140128800000♠7001401288 比特，反證完畢。（如果 KolmogorovComplexity 的代碼要更短一些，反證依然成立。如果它要更長，那麼 GenerateComplexString 中使用的常數也可以相應變大。）

以上使用的反證法類似於佩里悖論：「₁不 ₂能 ₃用 ₄少 ₅於 ₆二 ₇十 ₈個 ₉字 ₁₀定 ₁₁義 ₁₂的 ₁₃最 ₁₄小 ₁₅整 ₁₆數」。也可以使用停機問題 H 的不可計算性來推導 K 的不可計算性，因為 K 和 H 是圖靈等價的。

它的一個結論，在程序員群體中被幽默地稱為充分就業定理，其涵義之一是指不存在一個最優的規模優選編譯器。

柯氏複雜性的鏈式法則

柯氏複雜性的鏈式法則，是指：

K(X,Y) = K(X) + K(Y|X) + O(log(K(X,Y))).

它說明，能夠輸出 X 和 Y 的最短程序，相當於輸出 X 和已知 X 的情況下可以輸出 Y 的程序之和再加上一個對數參數。使用這個法則，可以定義柯氏複雜性的互信息近似。

數據壓縮

計算 K(s)的上界很簡單：只需要使用某種算法壓縮字符串 s ，再把所選語言中的壓縮算法加上壓縮後的字符串，它們的和就是長度上界。其實這就相當於給定語言中的自解壓縮檔。

如果一個字符串 s 的一個描述長度不超過 |s|−c 比特，則可以說這個字符串可以被壓縮掉 c 。這相當於說 K(s) ≤ |s|-c。否則的話，我們就說 s 不能被壓縮掉 c 。如果一個字符串不能被壓縮掉1，那麼我們就說這個字符串是 不可壓縮的 。根據鴿巢原理，每一個壓縮後的字符串對應唯一的壓縮前的字符串，所以不可壓縮串一定存在。因為長度為 n 的字符串有 2ⁿ 個，但是只存在 2ⁿ - 1 個長度小於 n 的字符串， (i.e. 長度可能為 0,1,...,n − 1)。

由於同樣的理由，大部分的字符串都是複雜的，也就是說難以被顯著地壓縮，它們的 K(s)並不比 |s|， s的長度小多少。準確地說，對於任意的 n ，有 2ⁿ 個長度為 n 的字符串。在這些字符串的樣本空間中的離散型均勻分布表明，對於每一個長度為 n 的字符串，權重為 2⁻ⁿ 。

定理：對於長度為 n 的字符串組成的樣本空間的離散型均勻分布來說，一個串不能被壓縮以 c 的概率至少為 1 - 2^−c+1 + 2⁻ⁿ。

證明：所有描述長度不超過 n-c 的字符串的數量，可以由以下等比數列得到：

1 + 2 + 2² + ... + 2^n-c = 2^n-c+1 - 1.

那麼，還剩下至少：

2ⁿ - 2^n-c+1 + 1

個長度為 n 的字符串不能夠被壓縮以 c 。對於單個字符串的概率，應該除以 2ⁿ 。

柴廷不完全定理

柯氏複雜性 K(s)，與兩個下界可計算函數 prog1(s), prog2(s)。橫坐標 (對數坐標) 列舉了所有字符串 s，以長度排序；縱坐標（線性坐標）使用比特來標示字符串的長度。大部分的串是不可壓縮的，也就是說它們的柯氏複雜度比它們的長度要多一個常數。圖中展示了17個不可壓縮的字符串，是幾乎垂直的那些線段。根據柴廷不完全定理，任何計算柯氏複雜性的下界的程序都不可能超過某個極限，且不取決於輸入的字符串 s。

我們已經知道，在所有可能的字符串里，大部分的串都是複雜的，也就是說它們不能被顯著地壓縮。然而，如果一個串的複雜度超過了某個閾值，則它不能被形式化地證明為複雜的。形式化的證明如下：首先，為自然數建立一個公理系統 S 。這個公理系統需要足夠強，可以判定關於字符串複雜度的斷言 A ，並且和 S 中的 F_A 相關聯。這個關聯需要有以下屬性：

如果 F_A可以被 S 中的定理證明，則相對應的斷言 A 為真。這個「形式化」可以用人工編碼例如哥德爾數的方法實現，或者依照對於 S 的預期解釋來進行形式化。

定理：存在一個常數 L （ L 僅取決於特定的公理系統以及描述語言的選擇），使得沒有任何一個 s 滿足以下情況：

K(s) ≥ L (在 S 中形式化)

可以在公理系統 S 中證明。

考慮到占多數的幾乎不可壓縮的串，大部分這樣的情況都會成立。

這個結論的證明脫胎於佩里悖論中使用的自指結構。使用反證法，如果定理不成立，則：

假設 (X): 對於任何整數 n ，存在一個字符串t s ，在 S 中存在不等式 "K(s) ≥ n"的一個證明。 (假設可以在 S 內形式化)。

我們可以使用以下方式列舉 S 中的所有形式化證明

  function NthProof(int n)

它接受輸入 n ，然後輸出一個證明。這個函數會列舉所有的證明，有一些證明是針對我們並不關心的一些公式，儘管在 S 的語言中所有可能的證明都是關於某個 n 的。其中有一些證明是針對複雜度公式 K(s) ≥ n，其中 s 和 n 都是語言 S 中的常數。以下程序

  function NthProofProvesComplexityFormula(int n)

可以確定，第 n 個證明是否證明了複雜度公式 K(s) ≥ n。字符串 s 和整數 L 分別可以由以下程序計算：

  function StringNthProof(int n)

  function ComplexityLowerBoundNthProof(int n)

考慮以下程序：

  function GenerateProvablyComplexString(int n)
     for i = 1 to infinity:
        if  NthProofProvesComplexityFormula(i) and ComplexityLowerBoundNthProof(i) ≥ n
           return StringNthProof(i)

對於給定的 n ，這個程序會嘗試所有的證明，直到找到一個字符串以及 S 中關於公式K(s) ≥ L （其中 L ≥ n）的形式證明。如果假設（X）成立，那麼這個程序會停止。這個程序的長度為 U. 存在一個整數 n₀ 使得 U + log₂(n₀) + C < n₀，其中 C 是以下程序的前綴：

   function GenerateProvablyParadoxicalString()
      return GenerateProvablyComplexString(n0)

（注意 n₀ 是直接包含在以上函數中的，而前面的 log₂(n₀) 已經包含了它） 程序 GenerateProvablyParadoxicalString 輸出的字符串 s ，存在一個 L 使得 K(s) ≥ L 可以在 S 中形式化證明，且 L ≥ n₀。所以，K(s) ≥ n₀ 成立。但是， s 也可以被長度為 U + log₂(n₀) + C 的程序描述，所以它的複雜度小於 n₀。以上矛盾證明了 假設 (X) 不能成立。

參見

• 柯爾莫哥洛夫公理
• 零一律
• 柯爾莫哥洛夫空間

延伸閱讀

• Blum, M. On the size of machines. Information and Control. 1967, 11 (3): 257. doi:10.1016/S0019-9958(67)90546-3. 
• Brudno, A. Entropy and the complexity of the trajectories of a dynamical system., Transactions of the Moscow Mathematical Society, 2:127{151, 1983.
• Burgin, M. (1982), "Generalized Kolmogorov complexity and duality in theory of computations", Notices of the Russian Academy of Sciences, v.25, No. 3, pp. 19–23.
• Cover, Thomas M. and Thomas, Joy A., Elements of information theory, 1st Edition. New York: Wiley-Interscience, 1991. ISBN 978-0-471-06259-2. 2nd Edition. New York: Wiley-Interscience, 2006. ISBN 978-0-471-24195-9.
• Lajos, Rónyai and Gábor, Ivanyos and Réka, Szabó, Algoritmusok. TypoTeX, 1999. ISBN 978-963-279-014-5
• Li, Ming and Vitányi, Paul. An Introduction to Kolmogorov Complexity and Its Applications. Springer. 1997. ISBN 978-0387339986.  First chapter on citeseer （頁面存檔備份，存於網際網路檔案館）
• Yu Manin, A Course in Mathematical Logic, Springer-Verlag, 1977. ISBN 978-0-7204-2844-5
• Sipser, Michael, Introduction to the Theory of Computation, PWS Publishing Company, 1997. ISBN 978-0-534-95097-2.
• Wallace, C. S. and Dowe, D. L., Minimum Message Length and Kolmogorov Complexity （頁面存檔備份，存於網際網路檔案館）, Computer Journal, Vol. 42, No. 4, 1999).
• 李明，[荷]P.M.B.威塔涅（Paul Vitanyi），描述複雜性，科學出版社，北京，1998
• Ming Li and Paul Vitanyi, An Introduction to Kolmogorov Complexity and Its Applications, 2nd Edition, Springer Verlag, 1997 （頁面存檔備份，存於網際網路檔案館）

外部連結

• The Legacy of Andrei Nikolaevich Kolmogorov
• Chaitin's online publications
• Solomonoff's IDSIA page （頁面存檔備份，存於網際網路檔案館）
• Generalizations of algorithmic information （頁面存檔備份，存於網際網路檔案館） by J. Schmidhuber
• Ming Li and Paul Vitanyi, An Introduction to Kolmogorov Complexity and Its Applications, 2nd Edition, Springer Verlag, 1997. （頁面存檔備份，存於網際網路檔案館）
• Tromp's lambda calculus computer model offers a concrete definition of K() （頁面存檔備份，存於網際網路檔案館）
• Universal AI based on Kolmogorov Complexity ISBN 978-3-540-22139-5 by M. Hutter: ISBN 978-3-540-22139-5
• David Dowe （頁面存檔備份，存於網際網路檔案館）'s Minimum Message Length (MML) （頁面存檔備份，存於網際網路檔案館） and Occam's razor （頁面存檔備份，存於網際網路檔案館） pages.
• P. Grunwald, M. A. Pitt and I. J. Myung (ed.), Advances in Minimum Description Length: Theory and Applications （頁面存檔備份，存於網際網路檔案館）, M.I.T. Press, April 2005, ISBN 978-0-262-07262-5.