@2026__30papers__Kolmogorov Complexity

# Kolmogorov Complexity > [!abstract] 概要 > 30papers が、「文字列を生成する最短プログラム」という記述長の基礎を体系化した教科書章として選んだソースである。原典は [[Thomas M. Cover]] と [[Joy A. Thomas]] の『Elements of Information Theory』第2版第14章であり、定義、不変性定理、Shannonエントロピーとの関係、非圧縮列、普遍確率、停止確率 \(\Omega\)、Occamの剃刀、コルモゴロフ十分統計量、最小記述長原理を扱う。(Source: [[.raw/articles/30papers-kolmogorov-complexity-2026-07-28]]; [30papers](https://30papers.com/papers/kolmogorov-complexity/); [Wiley](https://onlinelibrary.wiley.com/doi/abs/10.1002/047174882X.ch14)) ## ソース情報 - **30papers 掲載名**: Kolmogorov Complexity - **30papers 上の著者表記**: Cover, Thomas (Elements of Information Theory, Ch. 14) - **30papers 上の年**: 2006 - **30papers の位置づけ**: 文字列を生成する最短プログラムを扱い、記述長とアルゴリズム的ランダム性の形式的基礎を与える教科書章 - **実際の著者**: [[Thomas M. Cover]]、[[Joy A. Thomas]] - **原典**: 『Elements of Information Theory』第2版第14章、463–508頁 - **章DOI**: [10.1002/047174882X.ch14](https://doi.org/10.1002/047174882X.ch14) - **Wiley公式公開履歴**: オンライン2005-04-07、印刷2005-09-16 Wileyの本文PDFは認証なしの取得が403となった。公式ページで書誌・目次・章構成を確認し、技術内容は30papersの代表画像が示す第1版第7章の全体と章要点資料を照合した。そのため、定理の中核については確度が高い一方、第2版の本文表現を逐語確認できていないため、source全体のconfidenceはmediumとした。(Source: [[.raw/articles/30papers-kolmogorov-complexity-2026-07-28]]) ![[_attachments/30papers-kolmogorov-complexity/fig01-chapter-thumbnail.webp]] 30papersが掲載する代表画像。『Elements of Information Theory』1991年第1版の第7章「Kolmogorov Complexity」冒頭であり、30papersのリンク先である第2版第14章ではない。(Source: [30papers](https://30papers.com/papers/kolmogorov-complexity/)) > [!contradiction] 版・章番号・年の不一致 > 30papersは2006年の『Elements of Information Theory』第14章を指すが、代表画像はCopyright 1991・Chapter 7と明記された第1版である。またWiley公式の第2版第14章はオンライン・印刷とも2005年公開と記録される。2006は第2版の通称年・著作権年と考えられるが、30papers内で根拠は説明されていない。(Source: [[.raw/articles/30papers-kolmogorov-complexity-2026-07-28]]) > [!caution] 30papersの著者メタデータ > 30papersの表示用著者欄は「Cover, Thomas (Elements of Information Theory, Ch. 14)」だが、構造化データではカンマ分割により `Cover`、`Thomas (Elements of Information Theory`、`Ch. 14)` の3人物として誤登録されている。実際の著者は [[Thomas M. Cover]] と [[Joy A. Thomas]] である。(Source: [[.raw/articles/30papers-kolmogorov-complexity-2026-07-28]]) ## 定義と不変性固定した万能計算機 \(U\) に対し、文字列 \(x\) の[[コルモゴロフ複雑性]]は \[ K_U(x)=\min_{p:U(p)=x}l(p) \] であり、\(x\) を出力して停止する最短二進プログラムの長さである。条件付き複雑性 \(K_U(x\mid y)\) は、補助入力 \(y\) を与えたときの最短プログラム長である。(Source: [[.raw/articles/30papers-kolmogorov-complexity-2026-07-28]]) 任意の計算機 \(A\) に対し、ある万能計算機 \(U\) は \(K_U(x)\le K_A(x)+c_A\) を満たす。加法定数 \(c_A\) はシミュレータの記述長に相当し、\(x\) には依存しない。二つの万能計算機による複雑性の差も定数に抑えられるため、十分に長い文字列では計算機選択の影響を漸近的に無視できる。(Source: [[.raw/articles/30papers-kolmogorov-complexity-2026-07-28]]) ## 上界と非圧縮列文字列長が補助入力として与えられれば、文字列自身をプログラムへ埋め込めるため \(K(x\mid l(x))\le l(x)+c\) である。長さを与えない自己区切り記述では、さらにおよそ \(2\log l(x)\) のオーバーヘッドが加わる。したがって「短い規則で生成できる」ことは上界を示すが、その規則が最短であるとは限らない。(Source: [[.raw/articles/30papers-kolmogorov-complexity-2026-07-28]]) 長さ \(k\) 未満のプログラムは \(2^k\) 個未満しかないため、複雑性が \(k\) 未満の文字列も高々 \(2^k\) 個である。公平な \(n\) ビット列について、複雑性が \(n-k\) 以下となる確率は高々 \(2^{-k}\) であり、大半の文字列はほぼ圧縮不能である。(Source: [[.raw/articles/30papers-kolmogorov-complexity-2026-07-28]]) ## Shannonエントロピーとの関係コルモゴロフ複雑性は確率分布を仮定せず個々の文字列へ定義される。一方、Shannonエントロピーは分布に関する平均記述長である。有限アルファベットの独立同分布源では、 \[ \frac{1}{n}E[K(X^n\mid n)]\to H(X) \] となり、1記号当たりの期待最短プログラム長はShannonエントロピーへ収束する。(Source: [[.raw/articles/30papers-kolmogorov-complexity-2026-07-28]]) 下界は、停止する最短プログラムが接頭語自由でKraft不等式を満たし、平均符号長がエントロピー以上になることから得られる。上界は、標本の経験的型と、その型クラス内での標本の索引を記述する二段階符号から得られる。(Source: [[.raw/articles/30papers-kolmogorov-complexity-2026-07-28]]) ## 計算不能性一般に \(K(x)\) は計算できない。全ての短いプログラムを実行しても、停止していないプログラムが将来停止するかを有限時間で判定できず、最短性の認定は停止問題を解くことになる。具体的な圧縮や生成プログラムは上界を改善できるが、その上界が真値に到達したことを一般には証明できない。(Source: [[.raw/articles/30papers-kolmogorov-complexity-2026-07-28]]) この性質は、gzipを代理に使う[[@2026__30papers__Quantifying the Rise and Fall of Complexity in Closed Systems The Coffee Automaton]]の限界を基礎づける。圧縮に成功すれば短い記述の存在は示せるが、圧縮できなかったことだけでは非圧縮性の下界を示せない。(Source: [[.raw/articles/30papers-kolmogorov-complexity-2026-07-28]], [[@2026__30papers__Quantifying the Rise and Fall of Complexity in Closed Systems The Coffee Automaton]]) ## 普遍確率と停止確率文字列 \(x\) の普遍確率は \[ P_U(x)=\sum_{p:U(p)=x}2^{-l(p)} \] であり、ランダムな接頭語自由プログラムが \(x\) を出力する確率である。符号化定理は \[ K(x)=\log\frac{1}{P_U(x)}+O(1) \] を与え、短い記述を持つ対象ほど普遍事前確率が高いことを示す。(Source: [[.raw/articles/30papers-kolmogorov-complexity-2026-07-28]]) Chaitinの停止確率 \(\Omega=\sum_{p:U(p)\text{ halts}}2^{-l(p)}\) は、ランダムなプログラムが停止する確率である。停止プログラムは接頭語自由なので値は0と1の間にあるが、\(\Omega\) 自体は計算不能かつアルゴリズム的にランダムである。(Source: [[.raw/articles/30papers-kolmogorov-complexity-2026-07-28]]) ## 十分統計量と最小記述長コルモゴロフ構造関数は、文字列 \(x^n\) を含み、長さ \(k\) 以下のプログラムで生成できる集合 \(S\) のうち、\(\log|S|\) が最小のものを探す。\(k+\log|S|\) が \(K(x^n\mid n)\) に達する最小の \(k\) は、モデルの記述とモデル内の索引へ情報を分離する。対応するモデル生成プログラムがコルモゴロフ最小十分統計量である。(Source: [[.raw/articles/30papers-kolmogorov-complexity-2026-07-28]]) 第2版は最小記述長原理(MDL principle)を独立節として置く。短いモデルと、そのモデルを使った短いデータ記述の合計を選ぶ考え方であり、最短記述を統計的モデル選択へ接続する。(Source: [[.raw/articles/30papers-kolmogorov-complexity-2026-07-28]]) ## 評価 ### 強み - 確率分布を仮定せず、個々の対象の記述量を定義した。 - 万能計算機による差を加法定数へ閉じ込め、記述言語に依存しない漸近理論を与えた。 - Shannonエントロピー、普遍符号、普遍確率、統計的モデル選択を最短記述で結んだ。 - 非圧縮性、停止問題、\(\Omega\)を通じて「計算できない情報量」の境界を明確にした。 ### 限界 - 計算不能であり、実データに対する真の値を一般に求められない。 - 加法定数が支配する短い文字列同士の比較には向かない。 - 記述長の大きさは「興味深さ」や創発構造を直接表さず、一様ランダム列も最大級になる。 - 30papersのリンク先本文を認証なしで逐語確認できず、第1版と第2版の版差を完全には検証できない。 ## 関連 - 中心概念: [[コルモゴロフ複雑性]] - 著者: [[Thomas M. Cover]]、[[Joy A. Thomas]] - 創発的複雑性との区別: [[Complexodynamics]] - 計算可能な上界の利用例: [[@2026__30papers__Quantifying the Rise and Fall of Complexity in Closed Systems The Coffee Automaton]] ## 出典 - [[.raw/articles/30papers-kolmogorov-complexity-2026-07-28]] - [30papers: Kolmogorov Complexity](https://30papers.com/papers/kolmogorov-complexity/) - [Wiley: Elements of Information Theory](https://onlinelibrary.wiley.com/doi/book/10.1002/047174882X) - [Wiley: Chapter 14, Kolmogorov Complexity](https://onlinelibrary.wiley.com/doi/abs/10.1002/047174882X.ch14)