柯氏複雜性

在演算法資訊理論是衡量描述這個物件所需要的資訊量的一個尺度。柯氏複雜性是由安德雷·柯爾莫哥洛夫於1963年發現，所以用他的名字命名。以下面的兩個長度為64的字串為例。01010101010101010101010101010101010101010101010101010101010101011100100001100001110111101110110011111010010000100101011110010110第一個字串可以用中文簡短地描述為“重複32個‘01’”。第二個字串沒有明顯的簡短描述。一個字串formula_1的柯氏複雜性是這個字串的最短描述的長度。換言之，一個字串formula_1的柯氏複雜性是能夠輸出且僅輸出這個字串的最短計算機／圖靈機程式的長度。這樣的定義導致在使用不同的描述語言或者不同的圖靈機的時候柯氏複雜性不一樣。所以在討論柯氏複雜性的時候，通常都事先固定一個通用圖靈機formula_5作為參照。可以證明在使用formula_5做參照的時候，對任意的圖靈機formula_7，都存在一個僅決定於formula_5和formula_7的常數formula_10使得對所有的字串formula_1相對於formula_5的柯氏複雜性formula_13都滿足formula_18。根據這點，通常確定了一個參照圖靈機後就用formula_19和formula_20表示柯氏複雜性。不難證明，任何字串的柯氏複雜度都不會比字串自身的長度超過太多。類似與上文中的0101字串，它的柯氏複雜度和字串的長度關係不大，因此並不複雜。與康托爾的對角論證法、哥德爾不完備定理和圖靈的停機問題類似，柯氏複雜度的概念可以用於闡述和證明不可能性。定義.柯氏複雜度可以適用於任何數學概念，但是本文只針對字串。首先需要確定我們用以描述字串的語言，它可以基於任何計算機語言，例如LISP、Pascal或Java位元組碼。如果 P 是一個可以輸出字串 "x"的程式，則 P 是 "x"的描述。描述長度就等於程式 P 作為字串的長度，乘上每個字元的位元數。我們也可以使用圖靈機的編碼。每一個圖靈機 M 都對應一個字串 ＋"w" 就是 "x"的描述。這種描述更適合比較嚴謹的證明，通常是在正式研究中才會使用。在本文的討論中會使用比較非正式的描述。對於任何一個字串 "s" ，都存在至少一個描述。可以用以下程式表示：function GenerateFixedString()return "s"如果 "s" 的描述 "d"("s") 長度達到最小就是 "s"的“柯氏複雜度”，寫作 "K"("s")。可以表示為："K"("s") = |"d"("s")|.最小描述長度取決於選擇什麼語言來描述；但是改變描述語言所帶來的長度變化是有限的，這個屬性稱作不變性理論的一個例子。這個語言中的描述都會包括以下兩部分：更技術性的說法是，第一部分是一段計算機程式，如果把第二部分輸入這個程式，就會輸出該物件。不變性理論指的是：對於任意的描述語言 "L"，最優描述語言都至少和 "L" 同樣有效，但是會增加一段固定的字首。證明： 對於以"L"作為描述語言的任意一段描述 "D"，"D" 都可以轉換成為最優描述語言下的一段描述，這段描述包括將 "L" 描述為一段計算機程式 "P" 為：|"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 中的一個程式。直譯器有以下屬性：執行 codice_1 ，輸入 "p" 將會返回執行 "p" 的結果。然後，設 "L"2 中的程式 P 是 "s" 的最小描述，則 codice_1(P) 將會返回字串 "s"。而 "s" 的描述長度，是以下兩項之和：以上證明了所需的上界。歷史與背景.演算法資訊理論是計算機科學中的一個領域，研究柯氏複雜性和其他對於字串的複雜性度量。柯氏複雜性的理論和概念基於的一些關鍵性理論。1960年，所羅門諾夫發表了《歸納推理的通用性理論導論》，作為他所創立的的一部分。在1964年發表的《資訊與控制》的第一和第二部分 “歸納推理的正式理論” 中，他給出了一個更完整的描述。安德雷·柯爾莫戈洛夫稍後於1965年在 "Problems Inform. Transmission" 上獨立發表了這一理論。格里高利·柴廷也在 "J. ACM" 上發表了這一理論——柴廷的論文提交於1966年10月，於1968年12月修訂，引用了所羅門諾夫和柯爾莫戈洛夫的論文。這個理論認為，在所有從對字串的描述中解碼出字串的演算法裡，存在一個最優的演算法。這個演算法對於所有的字串來說，都可以得到和其他演算法同樣短的程式碼，除去一段固定的附加程式碼，這段程式碼不取決於字串，只取決於所選擇的演算法。所羅門諾夫用這個演算法和它所允許的程式碼長度，定義了一個字串的“普適機率”--，以對字元序列的歸納推斷作為基礎。柯爾莫哥諾夫利用這個理論定義了字串的很多屬性，包括複雜度、隨機度和資訊。當柯爾莫戈洛夫瞭解到所羅門諾夫的工作之後，承認了所羅門諾夫的發現在先。在很長一段時間內，所羅門諾夫的工作在蘇聯比在西方更為人知曉。科學界的共識一般是把和複雜度有關的工作歸功於柯爾莫戈洛夫，因為他主要研究序列的隨機程度；而演算法資訊理論的工作則歸功於所羅門諾夫，他主要集中研究用普適機率分佈來進行序列預測。這兩個領域的邊界，包括描述複雜度和機率通常被稱為柯爾莫戈洛夫複雜度。計算機科學家李明認為這是馬太效應的體現。柯爾莫戈洛夫複雜度或者演算法資訊理論有很多變體，其中一個廣泛應用的概念是“自生成程式”--，主要來自於。Mark Burgin基於布盧姆公理。基本結論.在以下討論中，我們用 "K"("s") 來表示字串 "s" 的複雜度。顯而易見，一個字串的最小描述不可能超過字串本身的長度太多。上文中的程式codice_4 可以輸出 "s" ，長度比 "s" 稍長。定理：存在一個常數 "c" ，使得：∀"s". "K"("s") ≤ |"s"| + "c"柯氏複雜性的不可計算性.定理：存在字串，擁有任意大的柯氏複雜度。嚴格表述為：對於任意 "n" ∈ ℕ，存在一個字串 "s" 的複雜度 "K"("s") ≥ "n"證明：反證。如果定理不成立，則任意的無限長字串，都可以使用有限個數，複雜性小於 "n" 位元的程式 來生成了。定理： "K" 不是一個可計算函式。也就是說，不存在一個程式，可以把字串 "s" 作為輸入，然後輸出它的 "K"("s")。證明：以下的反證法將使用類似Pascal語言的程式碼。為了證明的簡單起見，該語言的描述大概有 位元。下面開始反證法，假設有這樣一個程式存在：function KolmogorovComplexity(string s)它可以把字串 "s" 作為輸入，然後輸出它的 "K"("s")；簡單起見，假設這一函式的長度是 位元。現在考慮另一段長度為 位元的程式：function GenerateComplexString()for i = 1 to infinity:for each string s of length exactly iif KolmogorovComplexity(s) &gt;= 8000000000return s它將 codice_5 作為子程式，這個程式會從短到長檢查所有的字串，直到找到一個複雜度至少有 位元的字串 "s" 。這也就意味著，任何短於 位元的程式都不可能輸出這個字串。但是，以上的整個程式能夠輸出 "s" ，而其長度卻只有 位元，反證完畢。以上使用的反證法類似於：“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" 的字串有 2"n" 個，但是隻存在 2"n" - 1 個長度小於 "n" 的字串， (i.e. 長度可能為 0,1...,"n − 1)。由於同樣的理由，大部分的字串都是複雜的，也就是說難以被顯著地壓縮，它們的 "K"("s")並不比 |"s"|， "s"的長度小多少。準確地說，對於任意的 "n" ，有 2"n" 個長度為 "n" 的字串。在這些字串的樣本空間中的離散型均勻分佈表明，對於每一個長度為 "n" 的字串，權重為 2−"n" 。定理：對於長度為 "n" 的字串組成的樣本空間的離散型均勻分佈來說，一個串不能被壓縮以 "c" 的機率至少為 1 - 2−"c"+1 + 2−"n"。證明：所有描述長度不超過 "n"-"c" 的字串的數量，可以由以下等比數列得到：1 + 2 + 22 + ... + 2"n"-"c" = 2"n"-"c"+1 - 1.那麼，還剩下至少：2"n" - 2"n"-"c"+1 + 1個長度為 "n" 的字串不能夠被壓縮以 "c" 。對於單個字串的機率，應該除以 2"n" 。柴廷不完全定理.我們已經知道，在所有可能的字串裡，大部分的串都是複雜的，也就是說它們不能被顯著地壓縮。然而，如果一個串的複雜度超過了某個閾值，則它不能被形式化地證明為複雜的。形式化的證明如下：首先，為自然數建立一個公理系統 S 。這個公理系統需要足夠強，可以判定關於字串複雜度的斷言 A ，並且和 S 中的 FA 相關聯。這個關聯需要有以下屬性：如果 FA可以被 S 中的定理證明，則相對應的斷言 A 為真。這個「形式化」可以用人工編碼例如哥德爾數的方法實現，或者依照對於 S 的預期解釋來進行形式化。定理：存在一個常數 "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" 成立，那麼這個程式會停止。這個程式的長度為 "U". 存在一個整數 "n"0 使得 "U" + log2("n"0) + "C" &lt; "n"0，其中 "C" 是以下程式的字首：function GenerateProvablyParadoxicalString()return GenerateProvablyComplexString("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) 不能成立。