## 定義 **コルモゴロフ複雑性**は、あるビット列を出力する最小のプログラムの長さによってそのビット列の複雑さを定義する尺度である。nビットの完全にランダムな系列はいかなるプログラムを用いても圧縮できないため複雑さはnであるのに対し、`010101...`のような周期列を出力するプログラムは`Repeat 01 n times`のような形に圧縮でき、最もビット数が多い部分は自然数nの2進表現(log nのオーダー)となり、出力ビット数に比べて圧縮されている。計算科学ではこの他にも複雑度を測る尺度として、(1) 最小化されていないプログラムの長さ(問題の複雑性クラスP・NP等に応じた計算量を実際のアルゴリズム開発に適応させた実務的な尺度)、(2) パラメータ数(2024年時点の生成AIの典型であるGPT-4は約100兆個とされ、Transformerを学習させるニューラルネットの結合数・閾値数に対応する)が用いられる(Source: [[@2025__TJSAI__AIシステムの進化速度は指数関数を超えている]])。 万能計算機を変えたときの複雑性差は対象文字列に依存しない加法定数に抑えられる。有限アルファベットの独立同分布源では、1記号当たりの期待コルモゴロフ複雑性がShannonエントロピーへ収束する。ただし、最短プログラムの認定は停止問題を解くことになるため、一般の \(K(x)\) は計算不能である。(Source: [[@2026__30papers__Kolmogorov Complexity]]) ## 横断的知見 - [[@2025__TJSAI__AIシステムの進化速度は指数関数を超えている]] は、ランダム系列のコルモゴロフ複雑性が最大になる性質を、プログラム記述量を測る尺度として説明する。[[@2026__30papers__The First Law of Complexodynamics]] は、同じ性質が「興味深い構造」の測定では限界になることを示す。一様ランダムな文字列は圧縮不能でも「ランダム」と短く統計的に記述できるため、創発的複雑性には sophistication、典型性、計算資源制約を組み合わせる必要がある。(Source: [[@2025__TJSAI__AIシステムの進化速度は指数関数を超えている]], [[@2026__30papers__The First Law of Complexodynamics]]) - [[@2026__30papers__Quantifying the Rise and Fall of Complexity in Closed Systems The Coffee Automaton]] は、gzip圧縮サイズをコルモゴロフ複雑性の計算可能な上界として使い、細粒度状態のエントロピーと粗粒化状態の見かけの複雑性を比較した。非相互作用モデルは解析的に \(\log_2 n+\log_2 t+O(1)\) 以下と示せたが、相互作用モデルで高複雑性を主張するには圧縮器による上界では足りず、下界証明が必要である。(Source: [[@2026__30papers__Quantifying the Rise and Fall of Complexity in Closed Systems The Coffee Automaton]]) - [[@2026__30papers__Kolmogorov Complexity]] が示す非計算可能性は、[[@2026__30papers__Quantifying the Rise and Fall of Complexity in Closed Systems The Coffee Automaton]] がgzipを代理に使い、相互作用モデルの高複雑性を証明できなかった理由を理論的に位置づける。実用圧縮器は短い記述の存在による上界を与えるが、圧縮失敗から下界は得られない。(Source: [[@2026__30papers__Kolmogorov Complexity]], [[@2026__30papers__Quantifying the Rise and Fall of Complexity in Closed Systems The Coffee Automaton]]) - [[@2026__30papers__Kolmogorov Complexity]] の \(K(x)=\log(1/P_U(x))+O(1)\) は、短い説明へ大きい普遍事前確率を与えることでOccamの剃刀を形式化する。一方、[[@2026__30papers__The First Law of Complexodynamics]] は一様ランダム列も最大級の \(K(x)\) を持つため、「興味深い構造」には追加のモデル分解が必要だと示す。コルモゴロフ十分統計量は、モデルの記述とモデル内のランダムな索引を分ける接点になる。(Source: [[@2026__30papers__Kolmogorov Complexity]], [[@2026__30papers__The First Law of Complexodynamics]]) - [[@2026__30papers__A Tutorial Introduction to the Minimum Description Length Principle]]は、計算不能な最短プログラムに基づく理想化MDLを、制限したモデル集合に相対的な普遍符号へ置き換える。NMLは事後的な最尤符号に対する最悪ケースregretを最小化するため、[[最小記述長原理]]はコルモゴロフ複雑性の計算可能な近似値そのものではなく、最短記述の発想を統計的モデル選択へ実装する別の層である。(Source: [[@2026__30papers__A Tutorial Introduction to the Minimum Description Length Principle]], [[@2026__30papers__Kolmogorov Complexity]]) - Herbert A. Simon は 1962 年の "The Architecture of Complexity" で「構造がまったく冗長でない、すなわちどの側面も他の側面から推論できないならば、その構造は自らの最も単純な記述であり、提示はできてもより単純な構造では記述できない」と述べており、これは非圧縮性の主張と実質的に一致する。ただし関心の向きが逆である。[[@2026__30papers__Kolmogorov Complexity]] は最短プログラム長という尺度の定義と、その一般的な計算不能性という帰結に向かう。Simon は尺度を定義せず、現実の複雑システムが**なぜ実際に冗長なのか**を、(1) 少数種のサブシステムの組み合わせからなること、(2) 準分解可能で集約量だけが相互作用の記述に入ること(「空虚な世界仮説」)、(3) 時間経路を生成する微分法則への再符号化によって潜在的な冗長性を顕在化できること、の 3 点として構造的に列挙する。すなわち Simon は圧縮可能性を測る側ではなく、自然界の複雑システムが圧縮可能であることの原因の側を扱っている。(Source: [[@1996__MITPress__The Sciences of the Artificial - Chapter 8 The Architecture of Complexity - Hierarchic Systems]], [[@2026__30papers__Kolmogorov Complexity]]) ## 未解決の問い - コルモゴロフ複雑性・プログラムの長さ・パラメータ数という3つの複雑度尺度は、生成AIの実際の「進化速度」を測るうえでどれが最も適切な代理指標か、[[@2025__TJSAI__AIシステムの進化速度は指数関数を超えている]]は明示的な結論を出していない。 - パラメータ数の増大は学習速度(訓練コスト)に影響するが、学習済みネットワークの推論速度はTransformerのベクトル演算がGPU上でパラメータ数に依存しない速度で計算できると考えられている。この非依存性は、コルモゴロフ複雑性・プログラム長という尺度とどう整合するか。 - 決定論的な時間発展を初期状態・遷移規則・時刻 \(t\) だけで短く記述できる問題に対して、どの資源制約なら熱力学的なエントロピー増加と整合する尺度を与えられるか。 - 汎用圧縮器で得られる上界から、相互作用する物理系のコルモゴロフ複雑性に対する非自明な下界へ進むには、どの構造を証明に利用できるか。 - 万能計算機に由来する加法定数が無視できない短い対象について、実務上意味のある比較尺度をどう較正するか。 - 問題固有のモデル集合に制限した実用MDLが見逃す規則性を、計算不能な理想MDLとの差としてどう定量化できるか。 ## 関連 - [[シンギュラリティ]] — チップ集積度向上に伴うプログラム複雑度増大の議論の文脈 - [[Transformer]] — パラメータ数という複雑度尺度が適用される具体的アーキテクチャ - [[Complexodynamics]] — 圧縮不能性と創発的な構造を区別する応用問題 - [[最小記述長原理]] — 計算不能な最短プログラムの発想を普遍符号によるモデル選択へ縮約する原理 - [[Thomas M. Cover]]、[[Joy A. Thomas]] — 情報理論の教科書として体系化した著者 - [[状態記述と過程記述]] — 冗長性の利用による複雑性の記述の簡約を、尺度ではなく構造的原因の側から扱う概念 ## 出典 - [[@2025__TJSAI__AIシステムの進化速度は指数関数を超えている]] - [[@2026__30papers__The First Law of Complexodynamics]] - [[@2026__30papers__Quantifying the Rise and Fall of Complexity in Closed Systems The Coffee Automaton]] - [[@2026__30papers__Kolmogorov Complexity]] - [[@2026__30papers__A Tutorial Introduction to the Minimum Description Length Principle]] - [[@1996__MITPress__The Sciences of the Artificial - Chapter 8 The Architecture of Complexity - Hierarchic Systems]]