柯氏複雜性

在演算法資訊理論（電腦科學和數學的一個分支）中，一個物件比如一段文字的柯氏複雜性（亦作科摩哥洛夫複雜性、描述複雜性、科摩哥洛夫-柴廷複雜度、隨機複雜度，或演算法熵）是衡量描述這個物件所需要的資訊量的一個尺度。柯氏複雜性是由安德雷·科摩哥洛夫於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.