コロモゴロフ複雑性の「不変性」

【 コロモゴロフ複雑性の「不変性」】

コロモゴロフ複雑性\(𝐾_𝜑 (𝑦)\)の定義: 「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は、次からアクセスできます。

コメント

このブログの人気の投稿

マルレク・ネット「エントロピーと情報理論」公開しました。

初めにことばありき

人間は、善と悪との重ね合わせというモデルの失敗について