コルモゴロフ複雑性
殆どの文字列は、より「圧縮された」形では表現できないという意味で複雑である。しかしながら、文字列の長さがある閾値を超える場合、その文字列が複雑であることを形式的に証明することは出来ない、ということが言えてしまう。正確な定式化は以下の通り。まず、自然数を扱う特定の公理系 S を固定する。この公理系は次のことが出来る程度には強いものとする。即ち、S に含まれる式 FA を、文字列の複雑さに関する或る主張 A に関連付けることが出来る。この際、FAが S の公理から証明可能なら、これに対応する主張 A も真になるとする。この「定式化」に際しては、ゲーデル数化のような人工的な符号化を用いてもよいし、適用しようとする S をもっと明快に表現するような定式化を用いても良い。
定理:次の式(をS の中で定式化したもの)を公理系 S の中で証明できるように文字列 s を取れないような、定数 L(具体的な値は公理系と記述言語にのみ依存する) が存在する。
K ( s ) ≥ L . {\displaystyle K(s)\geq L.}
圧縮不能に近い文字列は大量にあることから、殆ど全ての場合にこの式は真である筈なことに注意されたい。
前述の例で示されたように明示的に文字列 x をプログラムに含めることができるので、すべての x に対してそのコルモゴロフ複雑性 Ku(x) は x 自体の長さ |x| を定数分以上越えることはない。 すなわち、
定理: 任意の u に対して、ある定数 c が存在して、任意の x に対して、
K u ( x ) ≤ | x | + c {\displaystyle K_{u}(x)\leq |x|+c}
が成り立つ。