Can you summarize the following document?
        
  柯氏複雜度可以適用於任何數學概念,但是本文只針對字串。首先需要確定我們用以描述字串的語言,它可以基於任何計算機語言,例如LISP、Pascal或Java位元組碼。如果 P 是一個可以輸出字串 "x"的程式,則 P 是 "x"的描述。描述長度就等於程式 P 作為字串的長度,乘上每個字元的位元數。(例如,對於 ASCII來說是7)  我們也可以使用圖靈機的編碼。每一個圖靈機 M 都對應一個字串 <M>。如果 M 是一個圖靈機,給它輸入字串 "w" 它會輸出字串 "x",那麼這段拼合起來的字串 <M>+"w" 就是 "x"的描述。這種描述更適合比較嚴謹的證明,通常是在正式研究中才會使用。在本文的討論中會使用比較非正式的描述。  對於任何一個字串 "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固定字首的意義上是通用的。

  "'定理"':設 "K" 和 "K" 是滿足 圖靈完備性的描述語言 "L" 和 "L"的複雜度函式,則存在一個常數 "c",僅取決於對於語言 "L" 和 "L" 的選擇,有:  證明:根據對稱性,可以證明存在一個常數 "c" 對於所有的字串 "s" 滿足:  然後,假設語言 "L" 中存在一個程式,相當於是 "L" 的直譯器:  其中 "p" 是 "L" 中的一個程式。直譯器有以下屬性:  然後,設 "L" 中的程式 P 是 "s" 的最小描述,則 codice_1(P) 將會返回字串 "s"。而 "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" 的複雜度。  顯而易見,一個字串的最小描述不可能超過字串本身的長度太多。上文中的程式codice_4 可以輸出 "s",長度比 "s" 稍長。  定理:存在一個常數 "c",使得:

  定理:存在字串,擁有任意大的柯氏複雜度。嚴格表述為:對於任意 "n" ∈ N,存在一個字串 "s" 的複雜度 "K"("s") ≥ "n"  證明:反證。如果定理不成立,則任意的無限長字串,都可以使用有限個數,複雜性小於 "n" 位元的程式 來生成了。  定理: "K" 不是一個可計算函式。也就是說,不存在一個程式,可以把字串 "s" 作為輸入,然後輸出它的 "K"("s")。  證明:以下的反證法將使用類似Pascal語言的程式碼。為了證明的簡單起見,該語言的描述(即其直譯器)大概有 位元。下面開始反證法,假設有這樣一個程式存在:  它可以把字串 "s" 作為輸入,然後輸出它的 "K"("s");簡單起見,假設這一函式的長度是 位元。現在考慮另一段長度為 位元的程式:  它將 codice_5 作為子程式,這個程式會從短到長檢查所有的字串,直到找到一個複雜度至少有 位元的字串 "s" 。這也就意味著,任何短於 位元的程式都不可能輸出這個字串。但是,以上的整個程式能夠輸出 "s",而其長度卻只有 位元,反證完畢。(如果 codice_5 的程式碼要更短一些,反證依然成立。如果它要更長,那麼 codice_7 中使用的常數也可以相應變大。)  以上使用的反證法類似於佩裡悖論:“不 能 用 少 於 二 十 個 字 定 義 的 最 小 整 數”。也可以使用停機問題 "H" 的不可計算性來推導 "K" 的不可計算性,因為 "K" 和 "H" 是圖靈等價的。  它的一個結論,在程式設計師群體中被幽默地稱為充分就業定理,其涵義之一是指不存在一個最優的規模優選編譯器。

  柯氏複雜性的鏈式法則,是指:  它說明,能夠輸出 "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" 的字串的數量,可以由以下等比數列得到:  那麼,還剩下至少:  個長度為 "n" 的字串不能夠被壓縮以 "c" 。對於單個字串的概率,應該除以 2 。

  我們已經知道,在所有可能的字串裡,大部分的串都是複雜的,也就是說它們不能被顯著地壓縮。然而,如果一個串的複雜度超過了某個閾值,則它不能被形式化地證明為複雜的。形式化的證明如下:首先,為自然數建立一個公理系統 S 。這個公理系統需要足夠強,可以判定關於字串複雜度的斷言 A,並且和 S 中的 F 相關聯。這個關聯需要有以下屬性:  如果 F可以被 S 中的定理證明,則相對應的斷言 A 為真。這個「形式化」可以用人工編碼例如哥德爾數的方法實現,或者依照對於 S 的預期解釋來進行形式化。  定理:存在一個常數 "L" ( "L" 僅取決於特定的公理系統以及描述語言的選擇),使得沒有任何一個 "s" 滿足以下情況:  可以在公理系統 S 中證明。  考慮到佔多數的幾乎不可壓縮的串,大部分這樣的情況都會成立。  這個結論的證明脫胎於佩裡悖論中使用的自指結構。使用反證法,如果定理不成立,則:  我們可以使用以下方式列舉 S 中的所有形式化證明  它接受輸入 "n",然後輸出一個證明。這個函式會列舉所有的證明,有一些證明是針對我們並不關心的一些公式,儘管在 S 的語言中所有可能的證明都是關於某個 "n" 的。其中有一些證明是針對複雜度公式 "K"("s") ≥ "n",其中 "s" 和 "n" 都是語言 S 中的常數。以下程式  可以確定,第 "n" 個證明是否證明了複雜度公式 "K"("s") ≥ "n"。字串 "s" 和整數 "L" 分別可以由以下程式計算:  考慮以下程式:  對於給定的 "n",這個程式會嘗試所有的證明,直到找到一個字串以及 S 中關於公式"K"("s") ≥ "L" (其中 "L" ≥ "n")的形式證明。如果假設(X)成立,那麼這個程式會停止。這個程式的長度為 "U". 存在一個整數 "n" 使得 "U" + log("n") + "C" < "n",其中 "C" 是以下程式的字首:  (注意 "n" 是直接包含在以上函式中的,而前面的 log("n") 已經包含了它) 程式 GenerateProvablyParadoxicalString 輸出的字串 "s",存在一個 "L" 使得 "K"("s") ≥ "L" 可以在 S 中形式化證明,且 "L" ≥ "n"。所以,"K"("s") ≥ "n" 成立。但是, "s" 也可以被長度為 "U" + log("n") + "C" 的程式描述,所以它的複雜度小於 "n"。以上矛盾證明了 假設 (X) 不能成立。
在演算法資訊理論(電腦科學和數學的一個分支)中,一個物件比如一段文字的柯氏複雜性(亦作柯爾莫哥洛夫複雜性、描述複雜性、柯爾莫哥洛夫-柴廷複雜度、隨機複雜度,或演算法熵)是衡量描述這個物件所需要的資訊量的一個尺度。柯氏複雜性是由安德雷·柯爾莫哥洛夫於1963年發現,所以用他的名字命名。