柯氏复杂度

在演算法資訊理論（電腦科學和數學的一個分支）中，一個物件比如一段文字的**柯氏複雜性**（亦作**科摩哥洛夫複雜性**、**描述複雜性**、**科摩哥洛夫 -柴廷複雜度**、**隨機複雜度**，或**演算法熵**）是衡量描述這個物件所需要的資訊量的一個尺度。柯氏複雜性是由安德雷・科摩哥洛夫於 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_1 和 _K_2 是滿足 圖靈完備性的描述語言 _L_1 和 _L_2 的複雜度函數，則存在一個常數 _c_ ，僅取決於對於語言 _L_1 和 _L_2 的選擇，有：

　
: ∀_s_. -_c_ ≤ _K_1(_s_) - _K_2(_s_) ≤ _c_.

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

　
: _K_1(_s_) ≤ _K_2(_s_) + _c_.

然後，假設語言 _L_1 中存在一個程式，相當於是 _L_2 的直譯器:

```
  **function** InterpretLanguage(**string** _p_)
```

其中 _p_ 是 _L_2 中的一個程式。直譯器有以下屬性：

　
: 執行 `InterpretLanguage` ，輸入 _p_ 將會返回執行 _p_ 的結果。

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

1. 程式 `InterpretLanguage` 的長度，可以看做常數 _c_。
2. **P** 的長度。根據定義，就是 _K_2(_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 語言的代碼。為了證明的簡單起見，該語言的描述（即其直譯器）大概有 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_|-_c_。否則的話，我們就說 _s_ 不能被壓縮掉 _c_ 。如果一個字串不能被壓縮掉 1，那麼我們就說這個字串是 _不可壓縮的_ 。根據鴿巢原理，每一個壓縮後的字串對應唯一的壓縮前的字串，所以不可壓縮串一定存在。因為長度為 _n_ 的字串有 2n 個，但是只存在 2n - 1 個長度小於 _n_ 的字串， (i.e. 長度可能為 0,1,...,_n − 1)。_ 

由於同樣的理由，大部分的字串都是複雜的，也就是說難以被顯著地壓縮，它們的 _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 。

 

## 柴廷不完全定理

我們已經知道，在所有可能的字串里，大部分的串都是複雜的，也就是說它們不能被顯著地壓縮。然而，如果一個串的複雜度超過了某個閾值，則它不能被形式化地證明為複雜的。形式化的證明如下：首先，為自然數建立一個公理系統 **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_0 使得 _U_ + log2(_n_0) + _C_ < _n_0，其中 _C_ 是以下程式的字首：

```
   **function** GenerateProvablyParadoxicalString()
      **return** GenerateProvablyComplexString(_n_0)
```

（注意 _n_0 是直接包含在以上函數中的，而前面的 log2(_n_0) 已經包含了它） 程式 GenerateProvablyParadoxicalString 輸出的字串 _s_ ，存在一個 _L_ 使得 _K_(_s_) ≥ _L_ 可以在 **S** 中形式化證明，且 _L_ ≥ _n_0。所以，_K_(_s_) ≥ _n_0 成立。但是， _s_ 也可以被長度為 _U_ + log2(_n_0) + _C_ 的程式描述，所以它的複雜度小於 _n_0。以上矛盾證明了 **假設 (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.