複雑さについて(3) コルモゴロフの複雑性

compositionality というのは、複雑なものが単純なものから構成されるという性質のことで、コンピュータのプログラムは、そうした性質を持つと書いた。
計算機科学の分野では、「複雑さ」の尺度に、「コルモゴロフの複雑性」と言う概念がよく用いられる。それは、ある対象の「複雑さ」を、その対象を出力するプログラムの「大きさ」に置き換えて説明しようというアイデアに基づいている。
簡単なものを出力するプログラムは短く、複雑なものを出力するプログラムは長い。これは、プログラマーなら経験的・直感的に理解できることだと思う。
また、これもプログラマーならわかると思うのだが、同じ結果を返すその意味では同じプログラムでも、ある人のプログラムは冗長で長く読みにくく、ある人のプログラムは、コンパクトでわかりやすい。
同じ結果を返すいくらでも冗長なプログラムはかけるのだから、出力の「複雑さ」を、プログラムの「大きさ」に対応づけようとするのなら、その結果を返す「最も短いプログラム」の大きさを考えるのがいいことになる。
ある対象の「コルモゴロフの複雑性」と言うのは、その対象を出力する「最も短いプログラム」の「大きさ」のことである。
もちろん、どの言語を選ぶか(Java, Python,Assembler, ....)、どのようなハードウェア・システム構成(GPUの有無、データベースの有無、 ...)を選ぶかで、この 「最も短いプログラム」の「大きさ」は変化する。
ただ、プログラムの実行環境を固定すれば、その環境のもとでの「コルモゴロフの複雑性」は、その意味では相対的にではあるが、一意に定まるはずである。
繰り返しになるが、ある対象の「コルモゴロフの複雑性」と言うのは、その対象を出力するプログラムの大きさが最小の自然数である。ある対象を出力する、同じ機能を持つ多数のプログラムがあったとしても、そのプログラム・サイズからなる自然数の全体の集まりを考えれば、その中に、最小の自然数が、一つは存在するはずである。
実行環境を固定しても、実際には、ある対象の「コルモゴロフの複雑性」を具体的に「計算」することは難しいかもしれない。この辺りが、「コルモゴロフの複雑性」がわかりにくいと感じられるところかもしれないのだが。
ただ、ここは「コルモゴロフの複雑性」理解の上で、飛躍が必要なポイントでもある。重要なことは、具体的にその数字を示すことができなくとも、また具体的にそのプログラムを示すことができなくとも、最小のプログラム・サイズが存在するのは確かであると言うことである。

コメント

このブログの人気の投稿

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

初めにことばありき

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