柯氏複雜性

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

基本介紹

• 中文名：柯氏複雜性
• 外文名：Kolmogorov-Chaitin complexity, stochastic complexity
• 又稱：柯爾莫哥洛夫複雜性
• 隸屬：計算機科學

定義

柯氏複雜度可以適用於任何數學概念，但是本文只針對字元串。首先需要確定我們用以描述字元串的語言，它可以基於任何計算機語言，例如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語言的代碼。為了證明的簡單起見，該語言的描述（即其解釋器）大概有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是圖靈等價的。

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

柯氏複雜性的鏈式法則

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

• 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+ 2。

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

• 1 + 2 + 2+ ... + 2= 2- 1.
  

那么，還剩下至少：

• 2- 2+ 1
  

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