セミナー紹介

全体概要

このセミナーは「コロモゴロフ複雑性とアルゴリズム論的情報理論」と題し、「ランダムさ」という直観的でありながら数学的に定義することが極めて難しい概念に、計算理論の枠組みから厳密な光を当てる試みです。

「ランダムさ」を定義することの困難は古くから認識されており、フォン・ノイマンは「ランダムな数というものは存在しない。あるのはランダムな数を生成する方法だけだ」と述べていました。ラプラスやフォン・ミーゼスによる古典的な定義の試みも、いずれも根本的な限界を持つことが示されます。この問題に新たな地平を開いたのが、1960年代のコロモゴロフとその学派であり、「オブジェクトの最短記述の長さ」として複雑性を定義するという画期的な発想が提示されます。

コロモゴロフ複雑性K(x)は「xを出力するプログラムの最小の長さ」として定義されますが、このシンプルな定義が深遠な結果を生み出します。複雑性は実行環境に依存しないという「不変性定理」が成立する一方、コロモゴロフ複雑性自体は「計算不能」であることが証明されます。さらにチャイティンは「どのような特定のビット列をとっても、そのコロモゴロフ複雑性がL以上であることを証明できないようなLが存在する」という不完全性定理を導き、複雑さへの人間の認識能力には根本的な限界があることを示しました。

アルゴリズム論的情報理論のパートでは、コロモゴロフ複雑性とシャノンのエントロピーという二つの「情報量」の間の深い関係性が探求されます。prefix-freeなプログラムの集合を用いた第二の定義を介することで、両者は定数の差の範囲内で一致することが示されます（レビンの定理）。さらにバエズとスティによる「アルゴリズム論的熱力学」では、プログラムの実行時間・長さ・出力という計算論的観測量を、統計力学のギブス・アンサンブルの枠組みに当てはめることで、古典的な熱力学と同じ方法論がアルゴリズム論的情報理論においても成立することが示されます。ランダムさの不思議から出発し、計算可能性・情報・熱力学が一つの枠組みの中で統合されていく、知的興奮に満ちたセミナーです。

講義のロードマップ

■ Part I: ランダムさの不思議

• この部の核心:

「ランダムさ」という概念に対して人間が持つ直観がいかに不確かであるかを示し、確率だけではランダムなものと非ランダムなものを区別できないという根本的な困難を提示します。量子論が自然の原理にランダムさが組み込まれていることを発見した文脈も参照しながら、数学的に厳密なランダムさの定義への動機づけを行います [p.3], [p.7]。

• 論理展開:
• コイントスの例で、30桁すべてが0の列も任意の「ランダムに見える」列も同確率(1/2)^30で出現するため、確率だけではランダムさを定義できないことを示す [p.10], [p.11]。
• 量子論の文脈で、ウィグナー・ダイソン・ボーム・ペンローズ・コンウェイらが人間の「意識」や「自由意志」と量子のランダムさの関係を論じてきた歴史を概観する [p.42], [p.43], [p.44], [p.45], [p.46]。
• ラプラスの「規則性をほとんど含まないもの」、フォン・ミーゼスの頻度的定義といった古典的試みが不完全であることを示す [p.48], [p.49], [p.50]。
• コロモゴロフらの新アプローチとして「オブジェクトの記述＝プログラム」「プログラムの長さ」「圧縮不可能性によるランダムさの特徴づけ」という三つの鍵概念を導入する [p.54], [p.55], [p.56], [p.57], [p.60], [p.61]。

■ Part II: 計算可能性理論とコロモゴロフの複雑性

• この部の核心:

コロモゴロフ複雑性を厳密に定式化し、その二つの根本的な性質──「不変性（実行環境への非依存性）」と「計算不能性」──を証明します。さらにチャイティンの不完全性定理により、複雑さの証明可能性には原理的な上限が存在することを示します [p.4], [p.65]。

• 論理展開:
• コロモゴロフ複雑性をK_φ(y) = min{|p| : φ(p) = y}として定義し、チャーチ＝チューリングの提言を根拠に「全ての計算可能な関数はプログラムで表現できる」ことを前提とする [p.70], [p.76]。
• 不変性定理: 任意のφに対してK_V(y) ≤ K_φ(y) + cを満たす「最適な」Vが存在することを示し、K(y) ≡ K_V(y)として実行環境に依存しないコロモゴロフ複雑性を定義する [p.85], [p.86], [p.87]。
• 計算不能性の証明: L(n) = K(k) ≥ 2nとなる最小のkを返す関数Lを仮定し、2n ≤ K(L(n)) ≤ K_L(L(n)) + c ≤ n + cという矛盾を導いてKの計算不能性を示す [p.92], [p.93], [p.94]。
• チャイティンの不完全性定理: 「複雑性がL以上であることを証明できないLが存在する」と「エレガントなプログラムであることは証明できない」という二つの形でまとめ、Lは数キロバイトという驚くほど小さい値に収まることを指摘する [p.97], [p.98], [p.99], [p.100], [p.101]。

■ Part III: アルゴリズム論的情報理論

• この部の核心:

アルゴリズム論的情報量の二つの定義（コロモゴロフ複雑性による第一の定義と、prefix-freeプログラムを用いた第二の対数的定義）を導入し、レビンの定理によって両者が定数差の範囲内で等価であることを示します。さらに統計力学のギブス・アンサンブルの方法を応用した「アルゴリズム論的熱力学」を構成し、計算論的観測量が古典的熱力学の観測量と完全に並行した構造を持つことを明らかにします [p.5], [p.110]。

• 論理展開:
• チャイティンのΩ（停止するプログラムの長さの指数和）とバエズのエントロピーS(n) = -log Σ_{x∈X, N(x)=n} 2^{-V(x)}を定義し、アルゴリズム論的情報量の出発点とする [p.117], [p.118]。
• 第一の定義（コロモゴロフ複雑性）と第二の定義の関係: nを出力するプログラムが一つだけなら両者は一致し、複数ある場合はS_second ≤ S_firstとなる。レビンの定理(1974年)によりS_second ≥ S_first - cも成立し、両者は定数差の範囲内で等価であることが確立される [p.124], [p.125], [p.126], [p.127]。
• アルゴリズム論的情報量への確率概念の導入: p_n = (1/Z) 2^{-V(x)}、Z = Σ_{x∈X} 2^{-V(x)}とおくことで、S(n) = -log p_n + log Zが成立し、アルゴリズム論的情報量はシャノンのinformation gainと定数差で対応することを示す [p.134], [p.135], [p.136], [p.137]。
• 統計力学のギブス・アンサンブルの方法を復習した上で、E(x)=実行時間の対数、V(x)=プログラムの長さ、N(x)=プログラムの出力という観測量に対して分配関数Z = Σ e^{-(E(x)+PV(x)-μN(x))/T}を構成し、共役変数(1/T, P/T, -μ/T)に対応する期待値の微分公式E=-∂lnZ/∂β等が成立するアルゴリズム論的熱力学を定式化する [p.161], [p.162], [p.163], [p.165]。