Kolmogorov complexity
この例のように言語による記述によって短くできる文字列がある一方で、圧縮できないような文字列も存在しており、文字列の説明の長さは文字列そのものの複雑さと関係していると考えられる。 このことをより形式的に取り扱うためにアルゴリズムという概念を用いて定式化されたものがコルモゴロフ複雑性である。