圧縮アルゴリズムで圧縮できない文字列

ふと抱いた疑問：連長（ランレングス）圧縮はランダムな入力に弱く，ランダムな入力に対しては出力の方が長くなりがちなことは有名．このことを一般化し...

任意の圧縮アルゴリズムに対して，出力が入力より長くなるような入力は構成できるか？

「任意の」というところは私の知識不足のせいで非常に広く曖昧になっているのだが，辞書式なら辞書式に制限して考える方がいいのかも．無論，存在を示すには無限降下列（？）が存在する筈ないことに注目することになろうが... ≦ のことを考えると．

可逆圧縮アルゴリズムだからM_CとM_DというTMの組で考えるべきだろう
D=R={0,1}^*で良い. 性質として任意のx∈{0,1}^*に対して x=M_D(M_C(x))が成立する
2の関係が成立する二つのTMの組の全体をCompと書くことにする.
問題は「「∀(M_C,M_D)∈Comp, ~~len(x) > len(M_C(x))~~len(x) < len(M_C(x))」となるxを構成できるか」である
M_CとM_Dを恒等関数 (何もしないTM) にするとこれはCompに入る.
なので任意のxについてlen(x)=len(ID(x))となるのでそのようなxは存在しない

自分で書いておきながら言うのもなんだが, 酷い論法だ. (;´Д｀)ですね.
こういう論法が出来るのはCompの定義が広いからである. 恒等関数を含むように定義して「圧縮アルゴリズム全体」と言い張るのはさすがに問題がある.

理論的な観点からはコルモゴロフ複雑性は関係しそう. ただ上の議論とは違って解凍アルゴリズム (というか解凍プログラム) は文字列xごとに決まるように定義してあるようだ. 成る程ね.

id:DASMさんへ. だってメモしたかったんだもの.

そして振り返らせてくれてありがとうございます.
上の議論と違わないんだと今, 気付いた. 上の複雑性では, 文字列xを圧縮したものとしてプログラムを出力するのがM_C. そのプログラムを実行してxを出力するM_D.

前半部の議論は俺の勘違いでした. コメント欄にあるとおり.