p101

圧縮できる場合

その前に，上のアイデアに関係した注意すべき問題点に少し触れておこう．まず上の例で見たような‘簡単な’ 規則性のある場合，情報圧縮をすると長さN のメッセージは長さ∼ logN に圧縮される．ところが，この長さは，もとのメッセージを生成する肝心のルール(たとえば０の次には１を書け，その後には０を書け．字数を数えて要求された字数になったらやめよ．このプログラムの大きさはN によらない) ではなくてメッセージの長さという‘つまらない’情報で決まっている．

 上に述べた二つの圧縮される数列の例を見ると，圧縮できる場合には少なくとも二つのかなり違った場合があることがわかる．ひとつは純形式的な構造がある場合，そしてもうひとつは‘意味’ がある場合．円周率の場合は純粋に数列の性質として圧縮できるとは考えにくい．それは別の世界(解析学の世界とか) で意味があるが故に圧縮できると見るべきであろう．これは乱雑性と複雑性の違いに関して意味のある観察である．