9/30 マルゼミ「計算科学とエントロピー」のお誘い
【 9/30 マルゼミ「計算科学とエントロピー」のお誘い】
今回のマルゼミ「計算科学とエントロピー」では、それら二つとは異なるエントロピーへのアプローチを取り上げます。「アルゴリズム論的情報理論 ("Algorithmic information theory")」といわれるものです。
「アルゴリズム論的情報理論」は、計算科学でのチューリングらの計算可能性の理論と、シャノンの情報理論とを結びつけようという試みです。
熱力学的エントロピーは、分子の運動の「乱雑さ」の尺度と考えられます。同じ「水」でも、水の分子が結晶上に規則的に並ぶ「氷」のエントロピーは低く、水の分子が自由に空中を飛び回る「水蒸気」のエントロピーは高くなります。
ビットの列で与えられる情報でも同じです。100個の"0"が連なるビット列は、規則的なのでエントロピーは低く、「ランダム」に、"0"と"1"が並ぶビット列は、エントロピーが高いと考えることができます。
ただ、この例え話は、実は、我々が何が「規則的」で何が「ランダム」かを判断できることを、暗黙のうちに仮定しています。「ランダムさ」でエントロピー を説明するのなら、「ランダムさ」とは何かを、きちんと説明できなければいけません。
あるビット列Xとビット列Yが与えられた時、次のように考えることにしましょう。 Xを出力するコンピュータ・プログラムの集まりをPX、Yを出力するコンピュータ・プログラムの集まりをPYとしましょう。（X,Yを出力するプログラムは一つとは限りません）
ここで、「プログラムの長さ」を考えます。Xを出力するコンピュータ・プログラムの集まりPXに属する全てのプログラムについて、その「長さ」を考え、その中で一番短いものの長さをx とします。同様に、Yを出力するプログラムで一番短いものの長さをy とします。
この時、プログラムの長さ x, y を比較して、x < y なら、ビット列Yはビット列Xより「複雑」だと考えます。要するに、あるビット列を出力する最小のプログラムの長さが大きければ大きいほど、そのビット列は、より複雑でよりランダムだと考えるのです。
先の例で言えば、100個の"0"が連なるビット列を出力するプログラムは（例えば、ループを使って）短く書けるが、「ランダム」に"0"と"1"が並ぶビット列を出力するプログラムは、短くは書けないということです。
ある出力Xを与えるプログラムの長さの最小値を、Xの「コロモロゴフの複雑性」と言います。「アルゴリズム論的情報理論」の出発点は、この「コロモロゴフの複雑性」です。
セミナーでは、次のトピックスを取り上げます。
● コルモゴロフの複雑性
● 情報圧縮の可能性と「ランダムさ」
● 複雑性の決定不可能性
● プログラムの「熱力学」
セミナーのお申し込みは、次のページからお願いします。
セミナーのまとめページは、こちらです。
セミナーの紹介ビデオは、こちらです。
コメント
コメントを投稿