複雑さについて（３） コルモゴロフの複雑性

compositionality というのは、複雑なものが単純なものから構成されるという性質のことで、コンピュータのプログラムは、そうした性質を持つと書いた。

計算機科学の分野では、「複雑さ」の尺度に、「コルモゴロフの複雑性」と言う概念がよく用いられる。それは、ある対象の「複雑さ」を、その対象を出力するプログラムの「大きさ」に置き換えて説明しようというアイデアに基づいている。

簡単なものを出力するプログラムは短く、複雑なものを出力するプログラムは長い。これは、プログラマーなら経験的・直感的に理解できることだと思う。

また、これもプログラマーならわかると思うのだが、同じ結果を返すその意味では同じプログラムでも、ある人のプログラムは冗長で長く読みにくく、ある人のプログラムは、コンパクトでわかりやすい。

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

ある対象の「コルモゴロフの複雑性」と言うのは、その対象を出力する「最も短いプログラム」の「大きさ」のことである。

もちろん、どの言語を選ぶか（Java, Python,Assembler, ....）、どのようなハードウェア・システム構成（GPUの有無、データベースの有無、 ...）を選ぶかで、この 「最も短いプログラム」の「大きさ」は変化する。

ただ、プログラムの実行環境を固定すれば、その環境のもとでの「コルモゴロフの複雑性」は、その意味では相対的にではあるが、一意に定まるはずである。

繰り返しになるが、ある対象の「コルモゴロフの複雑性」と言うのは、その対象を出力するプログラムの大きさが最小の自然数である。ある対象を出力する、同じ機能を持つ多数のプログラムがあったとしても、そのプログラム・サイズからなる自然数の全体の集まりを考えれば、その中に、最小の自然数が、一つは存在するはずである。

実行環境を固定しても、実際には、ある対象の「コルモゴロフの複雑性」を具体的に「計算」することは難しいかもしれない。この辺りが、「コルモゴロフの複雑性」がわかりにくいと感じられるところかもしれないのだが。

ただ、ここは「コルモゴロフの複雑性」理解の上で、飛躍が必要なポイントでもある。重要なことは、具体的にその数字を示すことができなくとも、また具体的にそのプログラムを示すことができなくとも、最小のプログラム・サイズが存在するのは確かであると言うことである。