柯氏複雜性

在計算機科學中，一個對象比如一段文字的柯氏複雜性（柯爾莫哥洛夫複雜性, 描述複雜性, Kolmogorov-Chaitin complexity, stochastic complexity, 算法熵）是衡量描述這個對象所需要的信息量的一個尺度。 以下面的兩個長度為64的字元串為例。
0101010101010101010101010101010101010101010101010101010101010101 1100100001100001110111101110110011111010010000100101011110010110 第一個字元串可以用中文簡短地描述為“重複32個‘01’”。第二個字元串沒有明顯的簡短描述。
一個字元串s的柯氏複雜性（C(s)或者K(s)）是這個字元串的最短描述的長度。換言之，一個字元串s的柯氏複雜性是能夠輸出且僅輸出這個字元串的最短計算機/圖靈機程式的長度。 這樣的定義導致在使用不同的描述語言或者不同的圖靈機的時候柯氏複雜性不一樣。所以在討論柯氏複雜性的時候，通常都事先固定一個通用圖靈機作為參照。