コルモゴロフ複雑性

コルモゴロフ複雑性：データの複雑さを測る尺度

コルモゴロフ複雑性とは、計算機科学において、有限長のデータ列の複雑さを定量的に評価するための指標です。あるデータ列を生成する最も短いプログラムの長さを、そのデータ列の複雑性と定義します。言い換えれば、データ列を表現するのに必要な情報の最小量を表していると言えるでしょう。この概念は、アンドレイ・コルモゴロフ、レイ・ソロモノフ、グレゴリー・チャイティンらによって1960年代後半に提唱され、アルゴリズム情報理論という新たな研究分野を開拓しました。

コルモゴロフ複雑性の定義

厳密には、万能計算機uを用いて、データ列xのコルモゴロフ複雑性Ku(x)は次のように定義されます。


Ku(x) = min{l(p) | u(p) = x}


ここで、pはuが実行するプログラム、l(p)はプログラムの長さ、u(p)はプログラムpの実行結果を表します。プログラムは入力を受け取らず、常に決まった出力を返すものとします。万能計算機とは、任意のアルゴリズムを実行できる計算機（例えば、C言語等の一般的なプログラミング言語処理系）を指します。

直感的な理解

例えば、「010101...」という60文字の文字列と、ランダムな60文字の2進数列を比較してみましょう。前者は「01を30回繰り返す」と簡単に記述できますが、後者にはそのような簡単な記述は存在しません。この例から、文字列の複雑さは、それを記述するのに必要な情報の量に関連していることが分かります。コルモゴロフ複雑性は、この直感を形式的に定式化したものです。

基本的な性質

自明な上限: データ列xに対して、そのコルモゴロフ複雑性Ku(x)は、xの長さ|x|を超えることはありません。常に、Ku(x) ≤ |x| + c (cは定数) が成り立ちます。これは、x自身をプログラムとして用いることができるためです。
記述言語による相対性: コルモゴロフ複雑性は、用いる万能計算機uに依存します。しかし、異なる万能計算機u1とu2の間では、Ku1(x)とKu2(x)の差は定数程度に収まります。これは、万能計算機が互いにエミュレートできるためです。

圧縮不能な文字列

Ku(x) ≧ |x| を満たす文字列xは「圧縮不能」と呼ばれます。驚くべきことに、このような文字列は多数存在します。長さnの文字列全体の集合において、圧縮不能な文字列は全体の半分以上を占めます。これは、短いプログラムで表現できる文字列よりも、圧縮できない文字列の方が多いことを意味します。つまり、ほとんどの文字列は、本質的に圧縮できません。

コルモゴロフ複雑性の計算不能性

コルモゴロフ複雑性Ku(x)を計算するアルゴリズムは存在しません。これは、停止問題の不確定性と密接に関連しています。もしKu(x)を計算できるならば、停止問題を解くアルゴリズムを構成できてしまうためです。この計算不能性は、データ圧縮の限界を示唆しています。

コルモゴロフ複雑性と関連する概念

データ圧縮の限界: コルモゴロフ複雑性は、データ圧縮の究極的な限界を示しています。ほとんどのデータ列は、そのコルモゴロフ複雑性まで圧縮することはできません。
ランダム性: 圧縮不能な文字列は、アルゴリズム的な規則性を持たないため、「ランダム」であるとみなせます。無限長の文字列においても同様の概念が定義され、アルゴリズム的にランダムな列という概念が生まれます。
* チャイティンの不完全性定理: ある程度以上の長さの文字列が複雑であることを、形式的に証明することは不可能です。これは、ゲーデルの不完全性定理と類似した結果であり、計算可能性の限界を示しています。

まとめ

コルモゴロフ複雑性は、データ列の複雑さを測る強力な概念であり、計算機科学、情報理論、数学の基礎といった様々な分野に影響を与えています。その計算不能性やチャイティンの不完全性定理といった性質は、計算可能性の限界を示す重要な結果であり、今後も研究が続けられていくでしょう。

もう一度検索