講演資料
講義資料スライドの表紙です。上のスライド画像をクリックすると、同じ画面のまま全編のPDF資料を快適に閲覧・印刷することができます。
セミナーの概要
このセミナーは「コロモゴロフ複雑性とアルゴリズム論的情報理論」と題し、「ランダムさ」という直観的でありながら数学的に定義することが極めて難しい概念に、計算理論の枠組みから厳密な光を当てる試みです。
「ランダムさ」を定義することの困難は古くから認識されており、フォン・ノイマンは「ランダムな数というものは存在しない。あるのはランダムな数を生成する方法だけだ」と述べていました。ラプラスやフォン・ミーゼスによる古典的な定義の試みも、いずれも根本的な限界を持つことが示されます。この問題に新たな地平を開いたのが、1960年代のコロモゴロフとその学派であり、「オブジェクトの最短記述の長さ」として複雑性を定義するという画期的な発想が提示されます。
コロモゴロフ複雑性K(x)は「xを出力するプログラムの最小の長さ」として定義されますが、このシンプルな定義が深遠な結果を生み出します。複雑性は実行環境に依存しないという「不変性定理」が成立する一方、コロモゴロフ複雑性自体は「計算不能」であることが証明されます。さらにチャイティンは「どのような特定のビット列をとっても、そのコロモゴロフ複雑性がL以上であることを証明できないようなLが存在する」という不完全性定理を導き、複雑さへの人間の認識能力には根本的な限界があることを示しました。
アルゴリズム論的情報理論のパートでは、コロモゴロフ複雑性とシャノンのエントロピーという二つの「情報量」の間の深い関係性が探求されます。prefix-freeなプログラムの集合を用いた第二の定義を介することで、両者は定数の差の範囲内で一致することが示されます（レビンの定理）。さらにバエズとスティによる「アルゴリズム論的熱力学」では、プログラムの実行時間・長さ・出力という計算論的観測量を、統計力学のギブス・アンサンブルの枠組みに当てはめることで、古典的な熱力学と同じ方法論がアルゴリズム論的情報理論においても成立することが示されます。ランダムさの不思議から出発し、計算可能性・情報・熱力学が一つの枠組みの中で統合されていく、知的興奮に満ちたセミナーです。
講義のロードマップ
ここでは、セミナーの講演資料がどのようなパートから構成されているかを示します。また、それぞれのパートのポイントを紹介します。
■ Part I: ランダムさの不思議
「ランダムさ」という概念に対して人間が持つ直観がいかに不確かであるかを示し、確率だけではランダムなものと非ランダムなものを区別できないという根本的な困難を提示します。量子論が自然の原理にランダムさが組み込まれていることを発見した文脈も参照しながら、数学的に厳密なランダムさの定義への動機づけを行います [p.3, p.7]。
■ Part II: 計算可能性理論とコロモゴロフの複雑性
コロモゴロフ複雑性を厳密に定式化し、その二つの根本的な性質──「不変性（実行環境への非依存性）」と「計算不能性」──を証明します。さらにチャイティンの不完全性定理により、複雑さの証明可能性には原理的な上限が存在することを示します [p.4, p.65]。
■ Part III: アルゴリズム論的情報理論
アルゴリズム論的情報量の二つの定義（コロモゴロフ複雑性による第一の定義と、prefix-freeプログラムを用いた第二の対数的定義）を導入し、レビンの定理によって両者が定数差の範囲内で等価であることを示します。さらに統計力学のギブス・アンサンブルの方法を応用した「アルゴリズム論的熱力学」を構成し、計算論的観測量が古典的熱力学の観測量と完全に並行した構造を持つことを明らかにします [p.5, p.110]。
ページのナビゲート