仮想的なプログラミング言語を想定してKolmogorov複雑度の計算不能性を証明する

メモ

書いた当時はよく分かっていなかったが，この文書が主張していることはChaitinの不完全性定理の亜種のすごいシンプルな形の説明である気がする．

もっと厳密な議論として，Kolmogorov複雑度の計算不能性に書き直した．

主張

$ \mathcal{U}上でKolmogorov複雑度を計算する関数$ K_\mathcal{U}は計算可能ではない．

用語

ここでは万能計算機とは適当なプログラミング言語と考えて良い．

ここでの計算可能とは単にそういう関数$ Kを構成することは出来ない．ぐらいの意味な気がする．SnO2WMaN.icon

すなわち，「実際には$ Kはあるが，それが入力に対して常に停止するかはわからない」の意味ではない気がする

証明

仮定: $ Kが計算可能であるとする．

すなわち，ある万能計算機$ u上で動作してかならず停止するfunction calcKC(s: string): intという関数があるとする．

当然ながら，calcKC(s)はどうにか有限長の長さのプログラムに収まるはずである．

無限に長いプログラムはないとする

同じく$ uで動作する次の関数generateComplexString(n)を考える

code:generateComplexString

function generateComplexString(n: int): string

for i = 1 to Infinity:

for s in { forall s | s.length == i }:

if n <= calcKC(s): return s;

else: continue;

generateComplexString(n)はKolmogorov複雑度が$ n以上の最短長の文字列を返す．

{ forall s | s.length == i }は文字列の長さがiのすべての文字列の集合を意味する．

使えるアルファベットを$ \Sigmaとするとこの集合の大きさは高々$ |\Sigma|^iで有限である．

この計算はいつかは終わる．（calcKCが計算可能なので）

プログラムgenerateComplexString(n)は以上の通り高々有限の長さで記述可能である．

以上をまとめて$ uで動作する次のプログラム$ P_{1000}を例として考えよう

$ Pの添字$ 1000はint z = 1000とすることを意味する．

code:CalcKolmogorovComplexity

function calcKC(s: string): int

// Kolmogorov複雑度を計算する

function generateComplexString(n: int): string

for i = 1 to Infinity:

for s in { forall s | s.length == i }:

if: n <= calcKC(s): return s;

else: continue;

int z = 1000;

function main():

console.out(generateParadoxialString(z))

$ uはかならずmain関数を呼び出し，console.outで文字列を出力すると約束する．

上の$ P_{1000}を実行すると，Kolmogorov複雑度が1000以上の最短長の文字列$ sが必ず出力される

$ zを自由に変えられるとすると，

プログラム$ P_{z}の長さ$ l(P_{z})は

calcKC(s)の実装文字数$ l_{\mathtt{cKC}}

generateComplexString(n)の実装文字数$ l_{\mathtt{gCS}}

int z = ?;の文字数$ 8 + \log_2 z

function main(): console.out(generateParadoxialString(z))の文字数$ l_{\mathtt{main}}

として

$ l(P_z) = l_{\mathtt{cKC}} + l_{\mathtt{gCS}} + 8 + \log_2 z + l_{\mathtt{main}}

$ P_{1000}を実行して得られた文字列$ sは

Kolmogorov複雑度が1000以上であるが，

ところが，$ sは$ P_{1000}を実行して得た文字列であるので，そのKolmogorov複雑度は定義より$ l(P_{1000})以下である．

すなわち

$ 1000 \leq K(s) \leq l(P_{1000})

$ 1000 \leq K(s) \leq l_{\mathtt{cKC}} + l_{\mathtt{gCS}} + 8 + \log_2 1000 + l_{\mathtt{main}}

$ 1000 \leq K(s) \leq l_{\mathtt{cKC}} + l_{\mathtt{gCS}} + 12 + l_{\mathtt{main}}

いま，例えば$ l_{\mathtt{cKC}} + l_{\mathtt{gCS}} + l_{\mathtt{main}}の部分が988文字以下だった場合，矛盾する．

実際，上の例では$ l_{\mathtt{cKC}}が700文字程度以下で実装できた場合，矛盾する．

$ P_{1000}で矛盾しなかったとしても，$ l_{\mathtt{cKC}} + l_{\mathtt{gCS}} + l_{\mathtt{main}}は有限の大きさなので，$ P_{1000},P_{1001},P_{1002},\dotsとどんどん大きくしていけば，いずれ矛盾する．

ここで$ \log_2 zの部分は増加のペースがとても遅いことに注意．

例えば，$ l(P_{1000}) = l(P_{9999})

その矛盾したプログラム$ P_{z}をもって，仮定は間違っていたと主張する．

すなわち

calcKCは実装不可能

Kolmogorov複雑度$ Kは計算不能である．

❏

参考文献

コルモゴロフ複雑性 - Wikipedia