コルモゴロフ複雑性
文字列 x が Ku(x) ≧ |x| となるなら x は「圧縮不能」であるという。 このような圧縮不能な文字列が存在するならどの程度存在するかを考えたい。 まず、簡単な基数 (濃度) についての考察から、ある長さの文字列 x すべての中には「圧縮不能」な文字列が少なくとも 1 つは存在していることがわかる。 なぜなら、長さ n のバイナリ列 (2 種類のアルファベットからなる文字列) は 2 個存在するが、 それより短いバイナリ列は長さ 0 も含めて 2 - 1 しか存在しないからである。さらに同じ理由で、長さ n 以下の 2 - 1 個のバイナリ列のうち、その半数より多い 2 が長さ n をもつのであるから、ある長さ以下のバイナリ列のうち圧縮不能な文字列は半数より多い。
一般に、圧縮不能の定義に自然数 c だけの余裕を入れ、Ku(x) ≧ |x| - c を満たすとした x を「c 圧縮不能」 という。 長さ n - c より短いバイナリ列の個数は、長さ n のバイナリ列と比べ、 (2 - 1) / 2 しかないので、 c 圧縮不能な文字列は全体の 1 - 1/2 より多い。 例えば、 c = 100 ビットだけ圧縮できるような文字列は、たかだか全体の 2 ∼ 10 しかない。
よって、ほとんどの文字列は文字列の長さと大きく違わないコルモゴロフ複雑性しかもたないだろうと結論できる。
コルモゴロフ複雑性(コルモゴロフふくざつせい、英語: Kolmogorov complexity)とは、計算機科学において有限長のデータ列の複雑さを表す指標のひとつで、出力結果がそのデータに一致するプログラムの長さの最小値として定義される。コルモゴロフ複雑度、コルモゴロフ=チャイティン複雑性 (Kolmogorov-Chaitin complexity) とも呼ばれる。
コルモゴロフ複雑性の概念は一見すると単純なものであるが、チューリングの停止問題やゲーデルの不完全性定理と関連する深遠な内容をもつ。コルモゴロフ複雑性やその他の文字列やデータ構造の複雑性の計量を研究する計算機科学の分野はアルゴリズム情報理論と呼ばれており、1960 年代末にアンドレイ・コルモゴロフ、レイ・ソロモノフ、グレゴリー・チャイティンによって創始された。