コルモゴロフ複雑性の計算不能性
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/06/19 04:09 UTC 版)
「コルモゴロフ複雑性」の記事における「コルモゴロフ複雑性の計算不能性」の解説
コルモゴロフ複雑性に関する計算理論上の興味深い帰結のひとつは、コルモゴロフ複雑性が実効的に計算できないということである。 定理： K は計算可能関数ではない。 言い換えれば、任意の文字列 s を入力として整数 K(s) を出力するようなプログラムは存在しない。証明は背理法による。以下、あるプログラムを構成し、そのプログラムから出力される文字列が、そのプログラムよりも長いプログラムからでなければ出力され得ないという矛盾を導く。次のようなプログラムがあるとしよう： function KolmogorovComplexity(string s) これは文字列 s を入力とし K(s) を返却する。ここで次のようなプログラムを考える。 function GenerateComplexString(int n) for i = 1 to 無限大: for each 長さが丁度 i である string s の全集合に対して if KolmogorovComplexity(s) >= n return s quit このプログラムは KolmogorovComplexity() をサブルーチンとして呼び出す。このプログラムは長さが1から無限大に至るまでのありとあらゆる文字列を調べ、コルモゴロフ複雑性が少なくとも n 以上であるような文字列を見つけたらそれを返す。従って、任意の正の整数 n について、これはコルモゴロフ複雑性が少なくとも n 以上であるような文字列を生成する。このプログラム自身は固定的な長さを持つが、その長さを U と書こう。プログラム GenerateComplexString() に対する入力は整数 n だが、この大きさは n を表すのに必要なビット数で測ることとすると、これは log2(n) である。さて、ここで更に次のようなプログラムを考える： function GenerateParadoxicalString() return GenerateComplexString(n0) このプログラムは GenerateComplexString() をサブルーチンとして呼び出すが、その際 n0 という任意の変数を引き渡す。このプログラムは コルモゴロフ複雑性が少なくとも n0 以上であるような文字列 s を出力する。このとき、n0 を適切に選ぶと矛盾を導くことができる。この値を選ぶに当っては、s が GenerateParadoxicalString() というプログラムによって生成される点に着目すると良い。このプログラムの長さは、たかだか U + log 2 ( n 0 ) + C {\displaystyle U+\log _{2}(n_{0})+C\quad } である（C は GenerateParadoxicalString() が GenerateComplexString() を呼び出す前後の固定部分の長さを表す）。n と log2(n) では前者の方が急速に増大することが明らかなので、ある n0 が存在して次の関係を満たす。 U + log 2 ( n 0 ) + C < n 0 . {\displaystyle U+\log _{2}(n_{0})+C<n_{0}.\quad } ところが、これは「少なくとも n0 以上の複雑性を持つ」ということの定義に反してしまう。何故なら K(s) の定義により、文字列 s を生成したプログラムの長さは少なくとも n0 以上はある筈なのに、s を生成した GenerateParadoxicalString() の長さは n0 よりも短いからである。以上より、"KolmogorovComplexity" というプログラムは、任意の文字列について複雑性を計算することは出来ないことが示された。 この証明は背理法によるが、ここで現れる矛盾はベリーのパラドックスに似ている：「n を30字未満では表現できない最小の正の整数としよう」。他の証明方法として、K が計算不能であることを停止問題 H が計算不能であることに帰着して示すこともできる。K と H はチューリング同値である。
※この「コルモゴロフ複雑性の計算不能性」の解説は、「コルモゴロフ複雑性」の解説の一部です。
「コルモゴロフ複雑性の計算不能性」を含む「コルモゴロフ複雑性」の記事については、「コルモゴロフ複雑性」の概要を参照ください。
- コルモゴロフ複雑性の計算不能性のページへのリンク
