柯氏複雜性

在演算法資訊理論（電腦科學和數學的一個分支）中，一個對象比如一段文字的柯氏複雜性（亦作柯爾莫哥洛夫複雜性、描述複雜性、柯爾莫哥洛夫-柴廷複雜度、隨機複雜度，或演算法熵）是衡量描述這個對象所需要的資訊量的一個尺度。柯氏複雜性是由安德雷·柯爾莫哥洛夫於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 是一個圖靈機，給它輸入字串 w 它會輸出字串 x，那麼這段拼合起來的字串 ＋w 就是 x的描述。這種描述更適合比較嚴謹的證明，通常是在正式研究中才會使用。在本文的討論中會使用比較非正式的描述。

對於任何一個字串 s，都存在至少一個描述。可以用以下程序表示：

```
 '''function''' GenerateFixedString()
    '''return''' ''s''
```

如果 s 的描述 d(s) 長度達到最小（即使用最少的比特數），它就可以稱為 s 的「最小描述」。同時，d(s)的長度（也就是這個描述使用的比特數）就是 s的「柯氏複雜度」，寫作 K(s)。可以表示為：

最小描述長度取決於選擇什麼語言來描述；但是改變描述語言所帶來的長度變化是有限的，這個屬性稱作不變性理論（invariance theorem）。

## 不變性理論

### 非正式表述

一些描述語言可以被稱作「最優的」（optimal）。它們有如下屬性：給定任意一個描述語言來描述一個對象，我們也可以用最優描述語言來描述該對象，只需要在原來的那段描述前面加上一段固定的前綴。這段前綴僅僅取決於使用哪一種描述語言，不取決於對對象的描述，也不取決於被描述的對象。

以下是「最優描述語言」（Optimal description language）的一個例子。這個語言中的描述都會包括以下兩部分：

- 第一部分描述了另一種描述語言。
- 第二部分是對象在那一種描述語言下的表述。

更技術性的說法是，第一部分是一段電腦程式，如果把第二部分輸入這個程序，就會輸出該對象。

不變性理論指的是：對於任意的描述語言 L，最優描述語言都至少和 L 同樣有效，但是會增加一段固定的前綴。

證明：對於以L作為描述語言的任意一段描述 D，D 都可以轉換成為最優描述語言下的一段描述，這段描述包括將 L 描述為一段電腦程式 P （前面提到的第一部分），然後將原來的描述 D 作為這段程序的輸入（第二部分）。新的描述 D』的長度（近似值）為：

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

### 更正式的描述

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

∀s. -c ≤ K1(s) - K2(s) ≤ c.

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

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

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

```
  '''function''' InterpretLanguage('''string''' ''p'')
```

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

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

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

- 程序 `InterpretLanguage` 的長度，可以看做常數 c。
- P 的長度。根據定義，就是 K2(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，使得：

### 柯氏複雜性的不可計算性

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

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

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

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

```
  '''function''' KolmogorovComplexity('''string''' s)
```

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

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

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

以上使用的反證法類似於佩里悖論：「1不 2能 3用 4少 5於 6二 7十 8個 9字 10定 11義 12的 13最 14小 15整 16數」。也可以使用停機問題 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

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

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

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

1 + 2 + 22 + ... + 2n-c = 2n-c+1 - 1.

那麼，還剩下至少：

2n - 2n-c+1 + 1

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

## 柴廷不完全定理

<image>

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

如果 FA可以被 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. 存在一個整數 n0 使得 U + log2(n0) + C < n0，其中 C 是以下程序的前綴：

```
   '''function''' GenerateProvablyParadoxicalString()
      '''return''' GenerateProvablyComplexString(''n''<sub>0</sub>)
```

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

## 外部連結

- 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.