Kolmogorov複雑性

1. 定義

1.1 Kolmogorov複雑性

K(x) = min{|p| : U(p) = x}

U: 万能チューリングマシン
p: プログラム
|p|: プログラムの長さ（ビット）

「xを出力する最短プログラムの長さ」

1.2 例

2. 基本性質

2.1 不変性定理

任意の2つの万能チューリングマシンU₁, U₂に対して:
|K_{U₁}(x) - K_{U₂}(x)| ≤ c

c: U₁とU₂のみに依存する定数

→ 定義はマシン選択に（定数を除いて）依存しない

2.2 計算不可能性

K(x)を計算するアルゴリズムは存在しない。

証明スケッチ（対角線論法）:
K(x)が計算可能と仮定
→ 「K(x) > n となる最小のx」を出力するプログラム
→ このxの複雑性は O(log n) だが K(x) > n
→ 矛盾

2.3 上界

K(x) ≤ |x| + c
（xをそのまま出力するプログラム）

ほとんどの長さnの文字列xに対して:
K(x) ≥ n - O(1)
（圧縮できない文字列が大多数）

3. MDL原理

3.1 最小記述長

MDL（Minimum Description Length）：

最良のモデルM* = argmin_M [L(M) + L(D|M)]

L(M): モデルの記述長
L(D|M): モデルを与えた下でのデータの記述長

→ オッカムの剃刀の形式化

3.2 モデル選択への応用

• 複雑すぎるモデル: L(M)が大きい
• 単純すぎるモデル: L(D|M)が大きい
• バランスの取れたモデルを選択

4. ランダム性

4.1 アルゴリズム的ランダム性

xがランダム ⟺ K(x) ≥ |x| - c

圧縮不可能 = ランダム = パターンがない

4.2 確率との関係

• 長さnの列の2^n個のうち、大部分は非圧縮
• 圧縮可能な列（パターンがある列）は稀
• Martin-Löfランダム性との等価性

5. 参考文献

• Kolmogorov (1965). "Three Approaches to the Quantitative Definition of Information"
• Li & Vitányi (2008). "An Introduction to Kolmogorov Complexity and Its Applications" 3rd ed.
• Grünwald (2007). "The Minimum Description Length Principle"