smoking186 https://blog.hatena.ne.jp/smoking186/ 186 @ hatenablog https://186.hatenablog.com/ CS ふと抱いた疑問：連長（ランレングス）圧縮はランダムな入力に弱く，ランダムな入力に対しては出力の方が長くなりがちなことは有名．このことを一般化し... 任意の圧縮アルゴリズムに対して，出力が入力より長くなるような入力は構成できるか？ 「任意の」というところは私の知識不足のせいで非常に広く曖昧になっているのだが，辞書式なら辞書式に制限して考える方がいいのかも．無論，存在を示すには無限降下列（？）が存在する筈ないことに注目することになろうが... ≦ のことを考えると． 可逆圧縮アルゴリズムだからM_CとM_DというTMの組で考えるべきだろう D=R={0,1}^*で良い. 性質として任意のx∈{0… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2F186.hatenablog.com%2Fentry%2F20080126%2F1201331745" title=" 圧縮アルゴリズムで圧縮できない文字列 - 186 @ hatenablog" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2008-01-26 16:15:45 rich https://186.hatenablog.com/entry/20080126/1201331745 1.0 100%