アルゴリズム情報理論：コルモゴロフ複雑性・ランダム性・圧縮性

中核概念

AITの中心的な量はコルモゴロフ複雑性である。これは、与えられた文字列を出力して停止する最短のコンピュータプログラムの長さを、文字数またはビット数で測ったものである。この長さは、選ぶプログラミング言語または万能機械に依存するため、結果は通常、加法定数までの違いを除いて述べられる。複雑性にはいくつかの変種がある。

• 通常のコルモゴロフ複雑性（C）：固定された万能機械上での最短プログラム長。
• 接頭辞複雑性（自己区切り複雑性、K）：プログラムが接頭辞自由集合をなす場合の最短長。確率的な文脈や符号化の文脈で有用である。
• アルゴリズム的ランダム性：文字列のコルモゴロフ複雑性がその長さに近いとき、その文字列はランダムとみなされる。すなわち、著しく短い記述を持たないことを意味する。

他の理論との関係

AITは古典的な（シャノン）情報理論を補完するが、それとは異なる。シャノンの枠組みは、ランダムな情報源に対する平均情報量と通信路の性質を測定し、多数の結果を効率よく符号化することに焦点を当てる。これに対しコルモゴロフ複雑性は、確率分布を持ち出すことなく、単一の対象に情報量を割り当てる。このためAITは、個別のデータ標本や、確率に由来しないランダム性の概念について考察するための道具を提供する。通常の情報理論および複雑性に関する議論と比較されたい。

歴史と発展

基礎となる考え方は、20世紀半ばに複数の研究者によって独立に発展させられた。アンドレイ・コルモゴロフは記述長を数学的に説明する複雑性の一形式を定式化し、レイ・ソロモノフ、グレゴリー・チャイティンらも関連する考え方を探究した。形式的な枠組みでは万能チューリング機械と不変性定理を用いる。不変性定理は、基礎となる万能機械を変更しても、複雑性の値が変化するのは有界な加法定数の範囲に限られることを保証する。初期の貢献者については、アンドレイ・コルモゴロフと関連研究を参照。

応用と意義

アルゴリズム情報理論は、理論と実践のいくつかの領域に影響を与えてきた。主な応用および用途には、次のものがある。

• データ圧縮：コルモゴロフ複雑性は、個々のファイルに対する圧縮の理想的な限界を形式化する。ただし、その厳密な値は計算可能ではない。
• ランダム性検定：ある列をランダムとして扱うべきかを判断するための客観的な基準を与える。
• 帰納的推論と機械学習：ソロモノフ帰納および最小記述長（MDL）の原理は、より短い説明を優先するためにアルゴリズム的単純さを利用する。
• 基礎論と哲学：AITは、オッカムの剃刀、確率、説明の本質をめぐる議論に寄与する。

限界、注目すべき結果と区別

コルモゴロフ複雑性は計算可能ではない。任意の文字列を入力として、その厳密な最短プログラム長を返すアルゴリズムは存在しない。この計算不可能性からは、数学的に定義可能でありながら既約的に複雑な対象の構成や、アルゴリズム的ランダム性を符号化する停止確率定数（チャイティンのオメガ）の存在など、多くの重要な帰結が導かれる。計算不可能であるにもかかわらず、AITは不変性に関する結果、および複雑性を圧縮可能性や確率的情報量と関連付ける保守的な境界評価により、堅牢な質的・量的洞察をもたらす。

実践的な場面では、AITはヒューリスティクスや評価法に着想を与える。圧縮可能性は複雑性の代理指標として用いられ、MDL型のモデル選択は実データに記述長の考え方を適用する。研究者は、アルゴリズム情報、エルゴード理論、統計力学、計算複雑性理論の結び付きを引き続き探究している。これらの結び付きは、データや理論が単純、ランダム、あるいは説明的であるとは、厳密な計算論的意味で何を指すのかを明らかにする助けとなる。

入門および追加の文献については、形式的定義と学習・ランダム性検定への応用を橋渡しする教科書や概説を参照するとよい。関連する主題には、計算可能性理論、コルモゴロフ複雑性の変種、アルゴリズム的確率がある。理論計算機科学および計算の項目にある議論も参照。

概説資料では、追加の参考文献やウェブ資料がプレースホルダーリンクで示されることが多い。情報、複雑性、通常の情報理論、ならびにコルモゴロフのような人物に関する伝記的・歴史的注記が該当する。