コルモゴロフ複雑性

ウィキペディア

索引トップ用語の索引ランキングカテゴリー

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/06/22 05:14 UTC 版)

関連する問題

データ圧縮の限界

(可逆な) 圧縮プログラムは与えられた文字列 x に関して、文字列 y を返す関数とみることができる。ただし y は対応する展開プログラムで x に復元できなければならない。よって、コルモゴロフ複雑性の定義から、展開プログラムの長さと y の長さの和は x のコルモゴロフ複雑性以上でなければならない。この意味でコルモゴロフ複雑性はその文字列データに対する究極的な圧縮を限界づけている。

通常、圧縮プログラムでは y の長さは x よりも小さくなることが期待されるが、上述の圧縮不能な文字列の議論は圧縮プログラムに関しても成立するので、実際には圧縮できない x が少なくとも半数存在し、ほとんどは大きな圧縮ができない。圧縮プログラムが我々が扱う多くの文字列を圧縮できるようにみえるのは、我々が実際に扱う文字列が、可能なすべての文字列と比べて極めて偏ったものにすぎないからである。

また、コルモゴロフ複雑性が計算不能であるという事実は、すべての文字列 x に対してコルモゴロフ複雑性がしめす究極の圧縮を実現するプログラムを作ることが原理的に不可能であるということを意味している。もしすべての文字列をコルモゴロフ複雑性まで圧縮するプログラムが存在すれば、その出力結果の長さを数えることでコルモゴロフ複雑性が計算できてしまい、上述の事実と矛盾するからである。

ランダム性

十分長い文字列において「圧縮不能」な文字列は、アルゴリズム化できるような何の規則性ももたないと考えられるので「ランダム」な文字列だとみなせるだろう。コルモゴロフ複雑性を無限長の文字列に拡張したとき、圧縮できないような文字列は「アルゴリズム的にランダムな列」 (algorithmically random sequence) と呼ばれている。正確には、与えられた無限列 x のすべての接頭部分列が c 圧縮不能であるような c が存在するとき、x はアルゴリズム的にランダムである。

有限列の場合と同様に濃度の議論から、プログラムは可算個しかないのに対して、無限長のバイナリ列は非可算個であるので、この意味で「ほとんどすべて」の無限列はアルゴリズム的にランダムである。しかしこのようなランダム列をプログラムによって生成することは決してできない。統計的にランダム性をもつように見える列、例えば疑似乱数列や、円周率のような計算可能な超越数、あるいは有限長で記述される初期状態をもつ記号力学系（英語版）が示すカオスなどは、すべてそれらを生成するプログラムが存在するので、この意味でのランダムではない。ランダムな文字列はその特定の文字列の説明の複雑さという直観を元にしたコルモゴロフの意味ではもっとも複雑となるが、ランダムな列のアンサンブルは逆に統計的に特徴づけることがもっとも簡単な文字列でもある。