コロモゴロフの複雑性を公開しました。

【「コロモゴロフの複雑性」を公開しました。】

9/30 マルゼミ「計算科学とエントロピー」 https://info-entropy4.peatix.com/ にむけたショートムービー「コロモゴロフの複雑性」を公開しました。ご利用ください。

ある出力Xを与えるプログラムの長さの最小値を、Xの「コロモロゴフの複雑性」と言います。「アルゴリズム論的情報理論」の出発点は、この「コロモロゴフの複雑性」です。

なぜ、「プログラムの長さの最小値」かといえば、同じ結果を返すいくらでも冗長なプログラムはかけるのですから、出力の「複雑さ」をプログラムの「大きさ」に一意に対応づけようとするのなら、その結果を返す「最も短いプログラム」の大きさを考えるのがいいことになるからです。

コロモゴロフの複雑性を、もう少しきちんと定式化するために、プログラムとその出力の関係をどう表現すればいいかを考えて見ましょう。そこには、プログラムの「実行」という考えが必要です。

プログラム pの出力が yだとします。このことは、ある実行環境のもとでプログラム pを「実行」すれば、出力 y が得られるということです。このことを、次のように表しましょう。
$$
𝜑(𝑝)=𝑦
$$
𝜑は、「ある実行環境でのプログラムの実行」を表しています。

この時、ある実行環境𝜑のもとでのプログラム p の実行の出力 yのコロモゴロフの複雑性𝐾_𝜑 (𝑦)は、次のように定義できます。
$$
𝐾_𝜑 (𝑦)=min⁡ \{ |𝑝| : 𝜑(𝑝)=𝑦 \}
$$ここで、minは最小値、|p|は、プログラム p の長さを表しています。

少し、形式的に関数の型を整理しましょう。

プログラム pを、0と1の有限のビット列 {0,1}*とし、
プログラムの出力のクラスをOで表すと、
$$𝜑 : {0,1}^*⟶ O$$
$$𝐾_𝜑 : O ⟶ ℕ$$です。

いくつか留意すべきことがあります。

ここでのプログラムpは入力を持っていません。
関数𝜑は、すべてのビット列 {0,1}*に対して定義されているわけではありません。

出力yのコロモゴロフの複雑性$𝐾_𝜑 (𝑦)$は、強く実行環境𝜑に依存しているように見えます。実際、どのプログラム言語を使うかで、プログラムの長さは変わりますから。

ただ、複雑性は、𝜑に依存しないことを示すことができるのです。
それは重要な性質です。それについては後で述べます。

過去・現在・未来