二つのアルゴリズム論的情報量の関係

【 二つのアルゴリズム論的情報量の関係 】

Xをプログラムの集合、𝑉(𝑥) をプログラムの長さ、𝑁(𝑥)をプログラムxの出力とすると、二つの情報量の定義は、次のようになります、

第一の定義 （コロモゴロフ複雑性）

$$𝑆_{𝑓𝑖𝑟𝑠𝑡} (𝑛) = min_{𝑥∈𝑋}⁡ \{ 𝑉(𝑥) : 𝑁(𝑥)=𝑛 \}$$

第二の定義

$$𝑆_{𝑠𝑒𝑐𝑜𝑛𝑑} (𝑛) = − log⁡ \sum_{𝑥∈𝑋, 𝑁(𝑥)=𝑛} 2^{−𝑉(𝑥) } $$

\(𝑆_{𝑓𝑖𝑟𝑠𝑡} (𝑛)と𝑆_{𝑠𝑒𝑐𝑜𝑛𝑑} (𝑛)\)の関係を考えてみましょう\( S(𝑛) = − log⁡ \sum_{𝑥∈𝑋, 𝑁(𝑥)=𝑛}2^{−𝑉(𝑥) } \) で、nを出力とするようなプログラムxが一つしかなかったとしましょう。総和の項は一つしかないということです。

この時、

$$𝑆_{𝑠𝑒𝑐𝑜𝑛𝑑 }(𝑛) = − log⁡ 2^{−𝑉(𝑥)} = 𝑉(𝑥)$$

となります。

nを出力とするようなプログラムxが一つしかないというのですから、V(x)は、𝑁(𝑥)=𝑛 を満たすプログラムの最小の長さになります。この時、

$$𝑆_{𝑠𝑒𝑐𝑜𝑛𝑑} (𝑛)=𝑆_{𝑓𝑖𝑟𝑠𝑡} (𝑛) $$ 

になります。

もちろん、nを出力するプログラムは、複数存在し得ます。この時、アルゴリズム論的情報量の第二の定義による、 \(𝑆_{𝑠𝑒𝑐𝑜𝑛𝑑} (𝑛)\)は、それらのプログラムの長さの項 \(− log⁡ 2^{−𝑉(𝑥)} \)が寄与しますので、その分、\(𝑆_{𝑓𝑖𝑟𝑠𝑡} (𝑛)\)より小さくなります。

$$𝑆_{𝑠𝑒𝑐𝑜𝑛𝑑} (𝑛)≤ 𝑆_{𝑓𝑖𝑟𝑠𝑡} (𝑛)$$

1974年に、Leonid Levinは、次のような定理を証明しました。すなわち、prefix free なプログラム言語については、すべてのnについて、次の式が成り立つような定数cが存在すると。

$$𝑆_{𝑠𝑒𝑐𝑜𝑛𝑑} (𝑛) ≥ 𝑆_{𝑓𝑖𝑟𝑠𝑡} (𝑛) − 𝑐$$

このことは、アルゴリズム論的情報量の定義として、第一の定義（コロモゴロフ複雑性）をとっても、第二のものをとっても、その違いは、高々、定数の範囲内に収まることを意味します。

今後、アルゴリズム論的情報量 \(S(n)\)の定義として、第二のものを使うことにしましょう。