コルモゴロフ複雑性
コルモゴロフ複雑性を定めるためには、文字列に対する形式的な記述言語をまず指定しなければならない。 このような記述言語としては何かの具体的なプログラミング言語を選べばよい。 あるプログラム言語 L を固定したとき、 L のプログラム p が有限長の文字列 x を出力するなら、p は x の「記述」であるということにする。
このとき特に p として x 自身を明示的に含むような自明な記述がある。 例えば、上記の前者の文字列を標準出力に出力する Perl プログラムは、
のようになるだろう。 このようなプログラムの長さは明らかに x の長さよりもある定数分だけ長くなる。 しかし文字列に何かの構造が発見できれば、適切なアルゴリズムを用いることによってより短いプログラムを作れるかもしれない。 例えば次のPerlプログラムは上と同じ文字列を出力する。
このように記述言語 L における文字列 x のあらゆる記述のうちで最小の長さをもつ記述が見出せたとするなら、その長さが L における x のコルモゴロフ複雑性となる。