コルモゴロフ複雑性
コルモゴロフ複雑性に関する計算理論上の興味深い帰結のひとつは、コルモゴロフ複雑性が実効的に計算できないということである。
定理: K は計算可能関数ではない。
言い換えれば、任意の文字列 s を入力として整数 K(s) を出力するようなプログラムは存在しない。証明は背理法による。以下、あるプログラムを構成し、そのプログラムから出力される文字列が、そのプログラムよりも長いプログラムからでなければ出力され得ないという矛盾を導く。次のようなプログラムがあるとしよう:
これは文字列 s を入力とし K(s) を返却する。ここで次のようなプログラムを考える。
このプログラムは KolmogorovComplexity() をサブルーチンとして呼び出す。このプログラムは長さが1から無限大に至るまでのありとあらゆる文字列を調べ、コルモゴロフ複雑性が少なくとも n 以上であるような文字列を見つけたらそれを返す。従って、任意の正の整数 n について、これはコルモゴロフ複雑性が少なくとも n 以上であるような文字列を生成する。このプログラム自身は固定的な長さを持つが、その長さを U と書こう。プログラム GenerateComplexString() に対する入力は整数 n だが、この大きさは n を表すのに必要なビット数で測ることとすると、これは log2(n) である。さて、ここで更に次のようなプログラムを考える:
このプログラムは GenerateComplexString() をサブルーチンとして呼び出すが、その際 n0 という任意の変数を引き渡す。このプログラムは コルモゴロフ複雑性が少なくとも n0 以上であるような文字列 s を出力する。このとき、n0 を適切に選ぶと矛盾を導くことができる。
定義から明らかなように、コルモゴロフ複雑性は記述言語あるいは万能計算機に依存する。 しかし、ある万能計算機 u1 から別の万能計算機 u2 にプログラムを移植しても、コルモゴロフ複雑性はたかだか(u1 と u2 によって決まる) 定数分しか増えない。なぜなら2つの万能計算機は、必ずもう一方の計算機をエミュレートできるからである。 u2 上で u1を模倣するエミュレーションプログラム ε1,2 を作り、その上で u1 のためのプログラム p を動かせば、結果として u2 の上でプログラム p を動かせたことになる。 そしてこのエミュレーションプログラムはエミュレートするプログラムの大きさにかかわらずつねに一定である。 従って、 u2 上でのコルモゴロフ複雑性はたかだか l(p) + l(ε1,2) である。 逆の場合も同様にエミュレートができるので、すなわち、
定理: 任意の万能計算機 u1, u2 に対し、ある定数 c1,2 が存在して、任意の x に対し、
| K 1 ( x ) − K 2 ( x ) | ≤ c 1 , 2 . {\displaystyle |K_{1}(x)-K_{2}(x)|\leq c_{1,2}.}
が成り立つ。
なおコルモゴロフ複雑性の議論では、記述言語の違いによりこのようなある定数分を除いて成立するという関係が頻出する。