コルモゴロフ複雑性の履歴
「ランダムっぽい」というのを計る指標はないかとググったら、これがひっかかった。
対象と同じものを出力するプログラムのうち最小のものが、その対象のコルモゴロフ複雑性となる。
例えば、
「010101010101010101010101010101010101010101010101」は
「print "010101010101010101010101010101010101010101010101"」としてプログラムを記述できるが元のデータより長くなる。
「print "01" x 24」とすれば元のデータより少ないデータ量で記述できる。なので、複雑性はたかだか「print "01" x 24」の文字数分となる。
よく読むと「ランダム性」というより、どれだけ圧縮可能かを求めるものみたい。
ちなみに、このコルモゴロフ複雑性は停止性問題と同様計算できない。
