柯氏複雜性
維基百科,自由的 encyclopedia
在演算法資訊理論(電腦科學和數學的一個分支)中,一個物件比如一段文字的柯氏複雜性(亦作科摩哥洛夫複雜性、描述複雜性、科摩哥洛夫-柴廷(英語:Gregory Chaitin)複雜度、隨機複雜度,或演算法熵)是衡量描述這個物件所需要的資訊量的一個尺度。柯氏複雜性是由安德雷·科摩哥洛夫於1963年發現,所以用他的名字命名。[1][2]
以下面的兩個長度為64的字串為例。
0101010101010101010101010101010101010101010101010101010101010101
1100100001100001110111101110110011111010010000100101011110010110
第一個字串可以用中文簡短地描述為「重複32個『01』」。第二個字串沒有明顯的簡短描述。
一個字串的柯氏複雜性(或者,區別如後)是這個字串的最短描述的長度。換言之,一個字串的柯氏複雜性是能夠輸出且僅輸出這個字串的最短電腦/圖靈機程式的長度。
這樣的定義導致在使用不同的描述語言或者不同的圖靈機的時候柯氏複雜性不一樣。所以在討論柯氏複雜性的時候,通常都事先固定一個通用圖靈機作為參照。可以證明在使用做參照的時候,對任意的圖靈機,都存在一個僅決定於和的常數使得對所有的字串相對於的柯氏複雜性(或者)和相對於的柯氏複雜性(或者)都滿足
- 。根據這點,通常確定了一個參照圖靈機後就用和表示柯氏複雜性(省略)。
不難證明,任何字串的柯氏複雜度都不會比字串自身的長度超過太多。類似與上文中的0101字串,它的柯氏複雜度和字串的長度關係不大,因此並不複雜。