圧縮アルゴリズムで圧縮できない文字列 2
続き. 少し考えて計算可能性を示す案を思いついた.
そもそもの野田さんの疑問 *1とは違うと思う上に面白く無い. まぁいいや, 書こう.
先ほどと同様に可逆圧縮アルゴリズム全体の集合を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}^*が存在}とする. これで置換も除去.
今, が与えられたときに出力長が短くなるyについてlen(y)=nとする. するとGusさんと同様の議論でnビット以下の文字列zについて必ず出力が長くなるものが存在する.
補題: 各に対して,
となるnビット以下の文字列zが存在する.
Gusさんと同様の議論を用いる.
とする.
今, とする. 出力長が短くなるyが存在するが,
と要素数は一致する. 従って出力長が長くなるzが
の中に存在する.
計算可能性の証明:
- M:入力 M_C:TM に対して (ただしM_CはComp^+に含まれる)
- i=0とする.
- iビットの文字列全てでM_Cを動作させる.
- もし出力長が長くなるものがあればそれを出力する.
- 無ければiを1増やしstep 2に戻る.
停止性は上の補題から言える. M_CをComp全体にしたときはどうしよう.
