複雑さについて（４） チャイティンの不完全性定理
コルモゴロフは、旧ソ連の数学者で、「コルモゴロフの複雑性」が定式化されたのは、1960年代半ばのこと。今から50年以上前の話だ。
「コルモゴロフの複雑性」が奇妙な性質を持つことを、驚くような形でまとめたのは、チャイティン(G. J. Chaitin)である。
「どのような特定のビット列をとっても、そのコルモゴロフの複雑性が L 以上であることを証明できないような数 L が存在する。」
これを「チャイティンの不完全性定理」という。
どう言うことか？
いくらでも複雑なものは存在する。どんな数に対しても、その数以上のコルモゴロフ複雑性を持つビット列は、無限に存在することを、我々は証明できる。ただ、特定のビット列が与えられた時、そのコルモゴロフ複雑性が L 以上であることを証明できない Lが存在すると言うのだ。
いくらでも複雑なものを、我々は、無限に考えることができる。複雑なビット列を考えて、それとは違うもっと複雑なビット列を考えて、もっと考えて、 ....... これを無限に繰り返しても、具体的なビット列を考える限り、その複雑さは L を超えないと言うのだ。
まるで、孫悟空がいくら飛び回っても、お釈迦様の手のひらから飛び出すことができないように。複雑さを求めて、宇宙の果てまで来たつもりだったのに、そこには超えられない壁 L があることを見つけたと言うことだ。
「複雑さ」（我々が具体的に考えうる）には、乗り越えられない壁 L があるのだ。
そういうと、Lは、とんでもなく巨大な数だろうと考えたくなるのだが、Lは、驚くほど小さいらしい。
compositionality というのは、複雑なものが単純なものから構成されるという性質のことだと書いたが、単純なものから複雑なものを構成するルールをが、Nビットで記述できるとすると、複雑さの壁 L は、
L ＜= N + 2359
程度だという。正確に、Lの値を求めることはできないが、あるコンピューター科学者は、数キロバイトだと推測している。
小さい！
特定のビット列を出力するプログラムは、そのビット列がどんなに複雑でも、数キロバイトに収まるということで、皆さんが普段作っているプログラムが、数キロバイトになるはずだということではないので、ご安心を。
チャイティンは、こういう言い方もしている。
「あるプログラムを、それより小さいサイズのプログラムが同じ出力を行うことがない時、"エレガント"と呼ぶことにしよう。あるプログラムが "エレガント" であることを、我々は証明できない。」
実際に、小さなプログラムでも、複雑なビット列を生み出すことができることの例を二つ紹介しよう。
一つ目は、マンデルブローのフラクタル図形の例である。この画像は、1ピクセルあたり24bitカラーを用いていて、全体で、162万bitあるのだが、これを生成するプログラムは、本当に小さい。
二つ目の例は、4K以下のプログラムサイズという制限のもとで、作品の出来を競う DemoSceneのコンテストで優勝した動画。見知らぬ惑星の描写だが、音楽含めて、プログラム・サイズは、たったの4Kだという。信じられない！
DemoSceneのコンテストは、現在は、名前を DemoScene Revision に変え、プログラムサイズ4K以下という制限以外にも、サイズ制限付きの複数のトラックで競技が行われている。2021年度のコンテストの結果は、こちらを見て欲しい。https://www.geeks3d.com/20210406/demoscene-revision-2021/
コメント
コメントを投稿