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

【コロモゴロフ複雑性の「計算不能性」】

コロモゴロフ複雑性には、重要な性質があります。

それは、コロモゴロフ複雑性は、xを出力するプログラムの最小の長さとして定義されるのですが、計算理論的には、それは「計算不能」です。

ここでは、そのことを見ていきましょう。

つぎのような関数Lを考えます。

　　𝐿(𝑛)=𝐾(𝑘)≥2𝑛 となるような最小の𝑘

関数 L : ℕ → 𝒪 は、nに対して、そのコロモゴロフ複雑性𝐾(𝑘)が2n 以上となるような最小の kを返します。もし、Kがすべてのnについて計算可能だとすると、Lもすべてのnについて計算可能です。

　　ここで、すべての𝑛に対して、𝐾(𝐿(𝑛))≥2𝑛 です。

なぜならば、すべての𝑛について、𝐿(𝑛)は、𝐾(𝐿(𝑛)) ≥ 2𝑛を満たす最小のものであるからです。

ここで、ある　V : 𝒪 → ℕ が、「最適」であるとしましょう。この時、𝐾=𝐾_𝑉 と書くことができます。前回見た「不変性定理」から、𝐾 ≤ 𝐾_𝐿 + 𝑐 である定数cが存在することがわかります。

　　𝐾_𝐿 の定義から、𝐾_𝐿 (𝐿(𝑛)) ≤ 𝑛 が成り立ちます。

なぜならば、𝐾_𝜑 (𝑦)=min⁡{ |𝑝| :𝜑(𝑝)=𝑦 } で、𝜑=𝐿として、

𝐾_𝐿 (𝐿(𝑛))=min⁡{ |𝑝| :𝐿(𝑝)=𝐿(𝑛) }となります。

𝑝=𝑛 の場合、L(𝑝)=𝐿(𝑛) が成り立つので、𝐾_𝐿 (𝐿(𝑛)) ≤ 𝑛 がいえます。

そうすると、次の不等式が成り立ちます。

　　2𝑛 ≤ 𝐾(𝐿(𝑛)) ≤ 𝐾_𝐿 (𝐿(𝑛)) + 𝑐 ≤ 𝑛 + 𝑐

　　2𝑛 ≤ 𝑛 + 𝑐 から 𝑛 ≤ 𝑐 ということになります。

ただし、この不等式は、全ての n については成り立ちません。𝑛 > 𝑐 なるnについては矛盾します。

Kがすべてのnについて計算可能だと仮定すると、矛盾が導かれるので、Kは計算可能ではありません。

------------

このショートムービーのpdfファイルは、次から利用できます。

セミナー「計算科学とエントロピー」のまとめページは、こちらです。

セミナーへのお申し込みは、次のサイトからお願いします。

過去・現在・未来