13.2 圧縮できない対象と計算不可能性

13.1 節は一つの自然数に $𝐾 U$ という尺度を与え，機械の選び方が定数のずれにしか効かないことを見た．尺度が定まったので，次は何が測れるかである．命題 13.1.6 はどの $𝑥$ についても $𝐾 U (𝑥) \leq | 𝑥 | + 1$ を与えていた．すなわち，どの対象も自分を書き写す長さでは書き出せる．問いは逆向きで，それより短く書き出せる対象がどれだけあるかである．

答えは数え上げから出る．短い指示は本数が限られているので，短く書き出せる対象も本数が限られている．本節の主張はすべてこの一行から出る．どんな長さをとってもそれ以上の複雑性をもつ対象があること（系 13.2.2）も， $𝐾 U$ の値を返す手続きが無いこと（定理 13.2.3）もそうである．

記述の短い対象を数える

定理 13.2.1. $𝑦, 𝑘 \in ℕ$ とすると，集合 ${𝑥 \in ℕ : 𝐾 U (𝑥 ∣ 𝑦) < 𝑘}$ は有限であり，その要素数は $2 𝑘$ より小さい．

証明. $𝑆 : = {𝑥 \in ℕ : 𝐾 U (𝑥 ∣ 𝑦) < 𝑘}$ とおく．各 $𝑥 \in 𝑆$ に対し，命題 13.1.5 より $| 𝑠 | = 𝐾 U (𝑥 ∣ 𝑦)$ かつ $U (𝑠, 𝑦) = 𝑥$ を満たすビット列 $𝑠$ があるので，そのようなものを一つ選んで $𝑠 𝑥$ と書く． $| 𝑠 𝑥 | = 𝐾 U (𝑥 ∣ 𝑦) < 𝑘$ である．

対応 $𝑥 \mapsto 𝑠 𝑥$ は単射である．というのも $𝑥, 𝑥' \in 𝑆$ が $𝑠 𝑥 = 𝑠 𝑥'$ を満たすなら， $U$ は部分関数で，値を持つならその値は一つだから， $𝑥 = U (𝑠 𝑥, 𝑦) = U (𝑠 𝑥', 𝑦) = 𝑥'$ となるからである．

長さが $𝑘$ 未満のビット列の本数を数える．長さ $𝑗$ のビット列は $2 𝑗$ 本だから， $𝑗 = 0, 1, \dots, 𝑘 - 1$ について足して

20 + 21 + \dots + 2 𝑘 - 1 = 2 𝑘 - 1

本である． $𝑆$ の元はこの $2 𝑘 - 1$ 本の中の相異なるビット列に写るから， $𝑆$ は有限で，その要素数は $2 𝑘 - 1$ 以下，とくに $2 𝑘$ より小さい． $◼$

形式化: 有限性 condComplexity_lt_finite，要素数の評価 condIncompressible_count (ソース)

数え方の要点は一つだけである．指示は対象を決めるが，対象は指示を決めない．それでも各 $𝑥$ に最短の指示を一つ選んでしまえば，選んだ先は相異なるので，対象の個数を指示の本数で抑えられる．そして指示はビット列だから，長さで区切れば本数が数えられる．長さが $𝑘$ 未満のビット列は $2 𝑘 - 1$ 本しかないので，複雑性が $𝑘$ 未満の対象も $2 𝑘 - 1$ 個までである．

系 13.2.2. $𝑦, 𝑘 \in ℕ$ とすると， $𝐾 U (𝑥 ∣ 𝑦) \geq 𝑘$ を満たす $𝑥 \in ℕ$ が存在する．

証明. そのような $𝑥$ が無いとすると，すべての $𝑥 \in ℕ$ が $𝐾 U (𝑥 ∣ 𝑦) < 𝑘$ を満たすので，定理 13.2.1 の集合は $ℕ$ の全体になる．ところが定理 13.2.1 よりその集合は有限であり， $ℕ$ は無限だから矛盾する． $◼$

形式化: exists_condIncompressible (ソース)

系 13.2.2 は，どれだけ大きな $𝑘$ をとっても， $𝑘$ ビット未満では書き出せない自然数があると言っている．この意味で圧縮できない対象はいくらでもある．ただし証明は，そのような $𝑥$ を一つも指していない．有限個しか無いはずの集合が全体になってしまう，という数え方の矛盾から存在を出しているだけである．指す手立てのほうは，次の定理 13.2.3 の証明が扱う．そこでは， $𝐾 U$ の値を返す手続きがあると仮定し，それを使って $𝐾 U (𝑥 ∣ 𝑦) \geq 𝑘$ を満たす $𝑥$ を探す手続きを組み立てて，矛盾を出す．

記述長を返す手続きはない

定理 13.2.3. $𝑦 \in ℕ$ とすると，自然数 $𝑥$ に $𝐾 U (𝑥 ∣ 𝑦)$ を対応させる関数は計算可能でない．

証明. $𝑦 \in ℕ$ を固定し， $𝑥 \mapsto 𝐾 U (𝑥 ∣ 𝑦)$ が計算可能だとする．

$𝑘 \in ℕ$ に対し， $𝐾 U (𝑥 ∣ 𝑦) \geq 𝑘$ を満たす $𝑥$ のうち最小のものを $𝑓 (𝑘)$ と書く．系 13.2.2 よりそのような $𝑥$ は存在するので， $𝑓 (𝑘)$ は定まる． $𝑓 (𝑘)$ は， $𝑥 = 0, 1, 2, \dots$ の順に $𝐾 U (𝑥 ∣ 𝑦)$ を計算して，値が $𝑘$ 以上になる最初の $𝑥$ を返す探索で求まり，この探索は必ず停止する．そこで $M (𝑧, 𝑦') : = 𝑓 (𝑧)$ （第 $2$ 引数は使わない）と定めると，Church–Turing のテーゼより $M$ は計算可能であり，とくに定義 13.1.3 の意味で機械である．

定理 13.1.7 をこの $M$ に当てて定数 $𝑏 \in ℕ$ をとる． $𝑘 \in ℕ$ とし， $𝑠$ を $𝑘$ の二進表示のビット列とすると， $𝑠$ が表す自然数は $𝑘$ だから $M (𝑠, 𝑦) = 𝑓 (𝑘)$ であり， $𝐾 U (𝑓 (𝑘) ∣ 𝑦) \leq | 𝑠 | + 𝑏 = | 𝑘 | + 𝑏$ である．いっぽう $𝑓 (𝑘)$ の定め方から $𝑘 \leq 𝐾 U (𝑓 (𝑘) ∣ 𝑦)$ である．二つを合わせると，すべての $𝑘 \in ℕ$ について

𝑘 \leq | 𝑘 | + 𝑏

が成り立つ．

これは $𝑘$ を大きくとると破れる． $𝑘 : = 2 𝑏 + 2$ とおくと， $2 𝑏 + 2$ の二進表示は $1$ の後ろに $0$ を $𝑏 + 2$ 個並べたものだから $| 𝑘 | = 𝑏 + 3$ であり，上の不等式は $2 𝑏 + 2 \leq 2 𝑏 + 3$ になる．ところが $𝑏$ についての帰納法より $2 𝑏 \geq 𝑏 + 1$ だから

2 𝑏 + 2 = 4 \cdot 2 𝑏 \geq 4 𝑏 + 4 > 2 𝑏 + 3

である．矛盾した． $◼$

形式化: condComplexity_not_computable (ソース)

この証明は Berry のパラドックスと呼ばれる古い言い回しを，そのまま定理にしたものである．「三十文字未満の日本語で言い表せない最小の自然数」という言い回しは，二十三文字でその数を言い表しており，自分自身に反している．証明の $𝑓 (𝑘)$ がこの言い回しにあたり， $𝑘$ を二進表示で書き下す $| 𝑘 |$ ビットが「三十文字」にあたる．言い回しのほうは「言い表せる」という言葉が曖昧なためにパラドックスにとどまるが， $𝐾 U$ の側ではその言葉が定義 13.1.4 で確定しているので，パラドックスは $𝐾 U$ が計算可能だという仮定への反証になる．

定理 13.2.3 が否定しているのは，すべての $𝑥$ について $𝐾 U (𝑥 ∣ 𝑦)$ の値を返す手続きの存在である．個々の $𝑥$ について上界を与えることは，命題 13.1.6 や定理 13.1.7 のとおりできる．できないのは，どの $𝑥$ についても与えた上界が最短だと確かめられる，一つの手続きを持つことのほうである．確かめようとすると，それより短い指示を試して，どれも $𝑥$ を出さないことを見なければならない．短い指示は有限本しかないのだから全部走らせればよさそうだが，走らせた指示が値を返さないとき，まだ返っていないのか永久に返らないのかを見分けなければならない．その見分けがつかないことは， $U$ についても言える．見分けがつくなら，短い指示から順に，止まると分かったものだけを走らせて最短のものを見つけられ，定理 13.2.3 に反するからである．本書はこれを，13.4 節で固定する別の機械についてだけ 13.5 節で書く．

書き写す長さとの隔たり

例 13.2.4（書き写す長さはほぼ達成される）. $𝑛 \geq 1$ とする． $0$ 以上 $2 𝑛$ 未満のどの自然数 $𝑥$ についても $𝐾 U (𝑥) \leq 𝑛 + 1$ であり， $0$ 以上 $2 𝑛$ 未満の自然数のうち少なくとも一つは $𝐾 U (𝑥) \geq 𝑛$ を満たす．

証明. 前半から見る． $𝑥$ を $0$ 以上 $2 𝑛$ 未満の自然数とする． $𝑥 = 0$ なら $| 𝑥 | = 0 \leq 𝑛$ である． $𝑥 \geq 1$ なら， $𝑥$ の二進表示の桁数を $𝑗$ として，先頭の桁が $1$ であることから $𝑥 \geq 2 𝑗 - 1$ であり， $2 𝑗 - 1 \leq 𝑥 < 2 𝑛$ と補題 8.2.5 より $𝑗 \leq 𝑛$ である．どちらの場合も $| 𝑥 | \leq 𝑛$ だから，命題 13.1.6 を $𝑦 : = 0$ に当てて $𝐾 U (𝑥) \leq | 𝑥 | + 1 \leq 𝑛 + 1$ を得る．

後半に移る．定理 13.2.1 を $𝑦 : = 0$ ， $𝑘 : = 𝑛$ に当てると， $𝐾 U (𝑥) < 𝑛$ を満たす自然数は $2 𝑛$ 個より少ない． $0$ 以上 $2 𝑛$ 未満の自然数はちょうど $2 𝑛$ 個あるから，そのすべてが $𝐾 U (𝑥) < 𝑛$ を満たすことはない． $◼$

例 13.2.4 の二つの評価の隔たりは $1$ ビットである．上からは， $𝑛$ ビットで書ける対象の複雑性はどれも $𝑛 + 1$ 以下で，これは命題 13.1.6 の書き写す上界にほかならない．下からは，そのうち少なくとも一つが $𝑛$ 以上で，これは定理 13.2.1 の数え上げから出る．つまり，書き写すという素朴な手続きは，最悪の対象については $1$ ビットしか損をしていない．機械を工夫する余地は，対象を選べば大きいが（例 13.1.9），すべての対象について一律に稼ぐことはできない．

ここまでの $𝐾 U$ は一つの自然数についての量で，分布は一度も出てこなかった．次節は，情報源から出た長さ $𝑛$ のブロックにこの量を当て， $1$ 文字あたりの平均が第2章のエントロピーに近づくことを示す．分布についての量と，一本の系列についての量が，そこで初めて結びつく．

InformationTheory — 形式化検証つき情報理論教科書（レビュー版）．数式は MathJax + AMS Euler で事前レンダリング．