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

続き. 少し考えて計算可能性を示す案を思いついた.
そもそもの野田さんの疑問 *1とは違うと思う上に面白く無い. まぁいいや, 書こう.

先ほどと同様に可逆圧縮アルゴリズム全体の集合をCompとする.
ただし今回はComp^+としてComp^+:={(M_C,M_D)|M_C,M_D:TM. 全てのx∈{0,1}^*についてM_D(M_C(x))=x. len(y)>len(M_C(y))となるy∈{0,1}^*が存在}とする. これで置換も除去.

今, M_Cが与えられたときに出力長が短くなるyについてlen(y)=nとする. するとGusさんと同様の議論でnビット以下の文字列zについて必ず出力が長くなるものが存在する.

補題: 各M_Cに対して, len(M_C(z))\gt len(z)となるnビット以下の文字列zが存在する.
Gusさんと同様の議論を用いる.
D_n:=\bigcup_{i=0}^{n} \{0,1\}^iとする.
今, R_n=M_C(D_n)とする. 出力長が短くなるyが存在するが, |D_n|=|R_n|と要素数は一致する. 従って出力長が長くなるzがD_nの中に存在する.

計算可能性の証明:

  • M:入力 M_C:TM に対して (ただしM_CはComp^+に含まれる)
    1. i=0とする.
    2. iビットの文字列全てでM_Cを動作させる.
    3. もし出力長が長くなるものがあればそれを出力する.
    4. 無ければiを1増やしstep 2に戻る.

停止性は上の補題から言える. M_CをComp全体にしたときはどうしよう.