直観的な例
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/06/19 04:09 UTC 版)
ある文字列が別の文字列よりも複雑であると言うためにはどうすればよいかという問題を考えよう。 例えば、同じ 60 文字の長さの 0, 1 からなる以下の 2 種類の文字列が与えられたとする。 010101010101010101010101010101010101010101010101010101010101 110010000110000111011110111011001111101001000010010101111001 これらを見比べると、直観的に前者の文字列はより簡単であって、後者の方はより複雑であると感じる。 この直観を明確にするひとつの方法として、文字列を言語で説明することを考えよう。 このとき前者は「01 の 30 回の繰り返し」と 11 文字で説明できる。 それに対して、後者はそのような簡単な説明が与えられそうもなく、説明するには文字列そのものを含めて 60 文字以上で記す他はないように思える。 この例のように言語による記述によって短くできる文字列がある一方で、圧縮できないような文字列も存在しており、文字列の説明の長さは文字列そのものの複雑さと関係していると考えられる。 このことをより形式的に取り扱うためにアルゴリズムという概念を用いて定式化されたものがコルモゴロフ複雑性である。 コルモゴロフ複雑性を定めるためには、文字列に対する形式的な記述言語をまず指定しなければならない。 このような記述言語としては何かの具体的なプログラミング言語を選べばよい。 あるプログラム言語 L を固定したとき、 L のプログラム p が有限長の文字列 x を出力するなら、p は x の「記述」であるということにする。 このとき特に p として x 自身を明示的に含むような自明な記述がある。 例えば、上記の前者の文字列を標準出力に出力する Perl プログラムは、 print "010101010101010101010101010101010101010101010101010101010101" のようになるだろう。 このようなプログラムの長さは明らかに x の長さよりもある定数分だけ長くなる。 しかし文字列に何かの構造が発見できれば、適切なアルゴリズムを用いることによってより短いプログラムを作れるかもしれない。 例えば次のPerlプログラムは上と同じ文字列を出力する。 print "01" x 30 このように記述言語 L における文字列 x のあらゆる記述のうちで最小の長さをもつ記述が見出せたとするなら、その長さが L における x のコルモゴロフ複雑性となる。
※この「直観的な例」の解説は、「コルモゴロフ複雑性」の解説の一部です。
「直観的な例」を含む「コルモゴロフ複雑性」の記事については、「コルモゴロフ複雑性」の概要を参照ください。
- 直観的な例のページへのリンク
