Kolmogorov Complexity
コルモゴロフ複雑性（Kolmogorov complexity）は、あるデータを生成できる最も短いプログラムの長さによって、そのデータの複雑さを測る情報理論の概念である。有限の文字列に対して定義され、ランダム性や圧縮可能性と密接に関連する。アンドレイ・コルモゴロフによって1960年代に導入されたこの概念は、アルゴリズム情報理論の基礎をなし、計算可能性理論や機械学習など幅広い分野に影響を与えている。
背景メモ
- Kolmogorov複雑性（コルモゴロフ複雑性）は、1960年代にソ連の数学者アンドレイ・コルモゴロフが提唱した情報理論上の概念。あるデータ（文字列）を生成する最も短いプログラムの長さを、そのデータの「複雑さ」の尺度とする。
- 例えば「010101...」と繰り返すだけのデータは短いプログラムで生成できるため複雑性が低いが、「完全にランダムな数字列」はそれ自体をそのまま出力するプログラム（データと同サイズ）が必要なので複雑性が最大になる。
- データ圧縮の理論的限界を示すと同時に、「ランダム性」を定義する数学的枠組みとしても重要。機械学習や統計的推論、哲学上のアルゴリズム情報理論の基盤となっている。
- ただし実際には「最も短いプログラム」を一般に計算するアルゴリズムは存在しない（停止性問題と等価）。そのため計算可能性の理論とも深く結びついている。
- 関連概念として、条件付きコルモゴロフ複雑性（あるデータが与えられた下での別データの複雑さ）や、アルゴリズム的十分統計量、Solomonoffの確率推論理論などがある。