続き. 少し考えて計算可能性を示す案を思いついた. そもそもの野田さんの疑問 *1とは違うと思う上に面白く無い. まぁいいや, 書こう.先ほどと同様に可逆圧縮アルゴリズム全体の集合をCompとする. ただし今回はとしてComp^+:={(M_C,M_D)|M_C,M_D:TM. 全てのx∈…

ふと抱いた疑問：連長（ランレングス）圧縮はランダムな入力に弱く，ランダムな入力に対しては出力の方が長くなりがちなことは有名．このことを一般化し... 任意の圧縮アルゴリズムに対して，出力が入力より長くなるような入力は構成できるか？ 「任意の」と…