## 定義 **コルモゴロフ複雑性**は、あるビット列を出力する最小のプログラムの長さによってそのビット列の複雑さを定義する尺度である。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システムの進化速度は指数関数を超えている]])。 ## 横断的知見 - 今後の取り込みで、複数ソース間の関係を追記する。 ## 未解決の問い - コルモゴロフ複雑性・プログラムの長さ・パラメータ数という3つの複雑度尺度は、生成AIの実際の「進化速度」を測るうえでどれが最も適切な代理指標か、[[@2025__TJSAI__AIシステムの進化速度は指数関数を超えている]]は明示的な結論を出していない。 - パラメータ数の増大は学習速度(訓練コスト)に影響するが、学習済みネットワークの推論速度はTransformerのベクトル演算がGPU上でパラメータ数に依存しない速度で計算できると考えられている。この非依存性は、コルモゴロフ複雑性・プログラム長という尺度とどう整合するか。 ## 関連 - [[シンギュラリティ]] — チップ集積度向上に伴うプログラム複雑度増大の議論の文脈 - [[Transformer]] — パラメータ数という複雑度尺度が適用される具体的アーキテクチャ ## 出典 - [[@2025__TJSAI__AIシステムの進化速度は指数関数を超えている]]