コロモゴロフ複雑性の「不変性」
【 コロモゴロフ複雑性の「不変性」】
コロモゴロフ複雑性\(𝐾_𝜑 (𝑦)\)の定義： 「yを出力するプログラムpの最小の長さ」の問題の一つは、この\(𝐾_𝜑 (𝑦)\)が、プログラムを実行する𝜑に強く依存していることです。
\(𝐾_𝜑 (𝑦)\) = min { |𝑝| : 𝜑(𝑝)=𝑦 }
事実、プログラムが Pythonで書かれているか、Javaで書かれているか、Assemblerで書かれているか, …. で、同じyを出力するプログラムの長さは、それぞれ違います。
ただ、任意の𝜑に対して、次の不等式を満たすVが存在することを示すことが出来ます。
$$𝐾_𝑉 (𝑦) ≤ 𝐾_𝜑 (𝑦) + 𝑐$$
ここで、cは定数です。（証明は、後に回します）
すべての𝜑に対して、この不等式を満たすVと定数cが存在することを、コロモゴロフ複雑性の「不変性定理」と呼びます。
この不等式を満たすVを「最適な」Vと呼ぶことにしましょう。
「不変性定理」は、 𝜑がいろいろ変わっても、\(𝐾_𝜑\) の(正確に言えば \(𝐾_𝜑 (𝑦) + 𝑐\) の)最小値𝐾_𝑉を与える 「最適な」Vが存在することを主張しています。
「不変性定理」で定義される「最適な」 V を使って、新しいコロモゴロフ複雑性 K(y)を次のように定義できます。
$$𝐾(𝑦)≡𝐾_𝑉 (𝑦)$$
この𝐾(𝑦)が、新しいコロモゴロフ複雑性の定義になります。
$$𝐾(𝑦)≡𝐾_𝑉 (𝑦) ≤ 𝐾_𝜑 (𝑦) + 𝑐$$
ですので、𝐾(𝑦)は、\(𝐾_𝜑 (𝑦)\)たちの取る値の最小値です。
もし、𝑉と𝑉 'が共に「最適」であるなら、
$$|𝐾_𝑉 (𝑦) − 𝐾_{𝑉′'} (𝑦)| ≤ 𝑐$$
が成り立ちます。
コロモゴロフは、論文”Three approaches to the quantitative definition of information” 1965 の中でこの定数について、次のように述べています。
「もちろん、特定の関数Vを考えることで、この定数cに関連した非決定性を避けることはできる。しかし、あからさまな恣意性抜きに、そうしたことができるかは疑わしい。
しかし、合理的な異なる「最適」な関数が、「複雑性の評価」に導き、それが数万ビットではなく、数百ビットに収斂すると想定しなくてはならない。
よって、例えば、「戦争と平和」のテキストの複雑性のような量は、ユニークなものとして定義されると推測することができる。」
ショートムービーお楽しみください。
スライドのpdfは、次からアクセスできます。
コメント
コメントを投稿