FC2ブログ

圧縮できる?

少々思うところありまして、
いろいろコルモゴロフ複雑性について考えていたのだけど。

こんなプログラミング言語を作る。
p=「00」を出力
q=「01」を出力
r=「10」を出力
s=「11」を出力

「0011011」を出力するには「pqrs」を実行すればいいように。
ただこのプログラムの長さを4とすると、
任意の2進列を半分の長さで記述できることになる。

これではおかしくなるので、
プログラムの長さもその2進列で計れば「pqrs」も
それぞれの記号が一度ずつ出現するので圧縮しようもなく、
2進列では各記号が2文字ずつ使うであろう、と。

なんかね、こういう話をしていると
圧縮可能な文字列というのが果たしてとらえきれる性質なのか
不安になってくる。
関連記事

コメントの投稿

非公開コメント

a8
最近の記事
月別アーカイブ
ブログ内検索
グリムス
フリーエリア
リンク
RSSフィード