13.4 自己限定万能機械と万能確率

13.3 節は，情報源が出した長さ $𝑛$ のブロックの複雑性を平均し，その値が $1$ 文字あたりでエントロピーに近づくことを示した．そこで測っていたのは分布から出た系列であり，主役は分布のほうだった．本節から先は分布を持ち出さない．以下に現れる対象は情報源ではなく，一つの自然数と一つの機械だけである．

13.3 節までの記述長は，一つの対象に最短の記述の長さを与えるものだった．見ているのは最短の一本だけで，同じ対象に短い記述が何本あるかは値に効かない．本節は測り方を裏返す．プログラムをでたらめに書いたとき，その対象が出てくる確率を，対象の重みとするのである．こう測れば，短い記述を持つ対象ほど重く，短い記述を何本も持つ対象はそのぶんさらに重い．二つの測り方は無関係ではなく，本節の定理 13.4.10 が，記述の短さと重みの大きさが係数 $2$ の範囲で互いを決めることを示す．この重みを情報源の分布に結びつける話，すなわちその対数を第12章の意味の万能符号の符号長として読む話は，本書では扱わない．

重みの作り方は素朴である．プログラムをでたらめなビット列だと思えば，投げたビットがちょうど $𝑠$ になる確率は $2 - | 𝑠 |$ だから， $𝑥$ を出すプログラム $𝑠$ についてこれを足し合わせればよい．足した値が確率として読めるためには，プログラムの側に一つ条件が要る．読む側が，渡されたビットをどこまで読めばプログラムが終わるかを，読んだ範囲だけで決められることである．プログラムが自分の終わりを自分で告げる，と言ってもよい．そうなっていれば，値を持つプログラムのどの一本も，他の一本の先頭には現れない．

定義 13.1.4 の $U$ はそうなっていない． $U$ は先頭が $0$ でその後ろが任意のビット列であるものすべてに値を持つので，たとえば $0$ も $00$ も値 $0$ を持ち，前者は後者の語頭（定義 4.1.2）である．終わりを告げる手立てがないぶん，同じ値を出すプログラムがいくらでも長く作れて，重みの和がそれに引きずられる．先頭が $0$ で長さが $𝑗 + 1$ のプログラムは $2 𝑗$ 本あるから，重みの和は長さごとに $1 / 2$ になり，全部足すといくらでも大きくなる．

そこで機械を取り替える．値を持つプログラムのどの一本も他の一本の語頭にならないような機械をとれば，重みの総和は $1$ を超えない．本節はそのような機械を一つ固定し，その機械についての記述長 $𝐾 V$ と重み $𝑃 V$ を定めて，二つが定数倍の範囲で互いを決めることを見る． $𝐾 U$ と $𝐾 V$ は別々の量だが無関係ではなく，命題 13.4.6 が両者を等式で結ぶ．固定する機械の作り方は，渡すビット列の長さを $1$ の個数で書くという最も素朴なものである．そのぶん前置きが記述と同じだけの長さを食い，係数 $2$ が本節から 13.6 節までの評価に残りつづける．前置きをもっと短く書く作り方はあるが，本書はこの一つだけを固定して，その係数ごと引き受ける．以下で係数 $2$ が，13.6 節で係数 $4$ が現れるのは，どれもこの一つの選択から来ている．

語頭のない集合

定義 13.4.1（語頭のない集合）. ビット列の集合 $𝑆$ が 語頭のない集合 であるとは， $𝑆$ の元 $𝑠$ と $𝑡$ について， $𝑠$ が $𝑡$ の語頭（定義 4.1.2）ならば $𝑠 = 𝑡$ が成り立つことをいう．

形式化: PrefixFree (ソース)

第4章定義 4.1.2 の語頭符号は，相異なる文字に与えた符号語のあいだに語頭の関係が無いことを要求していた．定義 13.4.1 はその条件を，符号語の集合そのものについて言い換えたものである．違いは二つある．写像ではなく集合について述べていることと，集合が無限であってよいことである．無限であってよいところが本節に効く．機械が値を持つプログラムは無限にあるからである．

和を一つ約束しておく．非負の実数を項とする可算個の和は，有限個の項を選んで足したものの全体の上限として定める（上に有界でなければ $+ \infty$ とする）．項が有限個のときは通常の和に一致すること，項の並べ方に依らないこと，項ごとに大小があればそのまま和の大小になることを既知とする．この約束を使うのは，本節の補題 13.4.2，定義 13.4.8，命題 13.4.9，定理 13.4.10 と例 13.4.11，13.5 節の定義 13.5.4，命題 13.5.5，補題 13.5.7，定理 13.5.8 と例 13.5.9，および第14章 14.6 節の定義 14.6.6 である．これらの和を実数として扱うのは，本章では命題 13.4.9 と命題 13.5.5 で値が $1$ 以下であることを示したあとだけである．第14章 14.6 節が実数として扱うのは別の上界を通してで，そちらは出力アルファベットの大きさの対数で和を抑える．

形式化上の注記（本節と 13.5 節に共通）. いま約束した和は，形式化ではどれも拡張非負実数の値として定義されている．そちらでは和が有限であることを先に示さずに書けるので，本文が上限として置いた定義の段は形式化に現れない．有限部分和の上限をとる段そのものは，形式化の証明にはそのまま現れる．13.5 節の定義 13.5.6 が $0$ 以上の実数について書く条件も，形式化では同じ拡張非負実数の上の述語として書かれている．

補題 13.4.2. $𝑆$ を，空列を含まない定義 13.4.1 の意味の語頭のない集合とすると

\sum 𝑠 \in 𝑆 2 - | 𝑠 | \leq 1

が成り立つ（ $𝑆$ は無限であってよい）．

証明. $𝑆'$ を $𝑆$ の有限部分集合とする． $𝑆'$ を有限アルファベット， $𝐷 : = 2$ とし， $𝑠 \in 𝑆'$ にその列自身を対応させる写像を $𝑐$ とする． $𝑆$ は空列を含まないから $𝑐 (𝑠)$ は ${0, 1}$ の文字を並べた空でない有限列であり， $𝑐$ は定義 4.1.1 の意味で $𝑆'$ 上の二元情報源符号である．相異なる $𝑠, 𝑡 \in 𝑆'$ について $𝑐 (𝑠) = 𝑠$ が $𝑐 (𝑡) = 𝑡$ の語頭だとすると，定義 13.4.1 より $𝑠 = 𝑡$ となって相異なることに反するから， $𝑐$ は語頭符号である．よって定理 4.2.1 より $\sum 𝑠 \in 𝑆' 2 - | 𝑠 | \leq 1$ である．

$𝑆$ にわたる和を有限部分和の上限として定めたことから，主張の左辺はいま抑えた有限和の全体の上限であり，どの有限和も $1$ 以下だから，上限も $1$ 以下である． $◻$

形式化: PrefixFree.tsum_inv_two_pow_length_le_one (ソース)

補題 13.4.2 は Kraft の不等式（定理 4.2.1）を，無限の符号語の集合へ広げたものにほかならない．第4章では符号語の本数が有限だったので，長さがいちばん長い符号語をとって木の深さを固定できた．集合が無限だとその深さがとれないので，有限部分集合ごとに第4章の不等式を当て，上限をとって全体に広げる．上限をとる操作が入るぶん，等号がどこで成り立つかの話は落ちるが， $1$ 以下という上界はそのまま残る．空列を含まないという仮定は，定理 4.2.1 を経由するために要る条件であって，結論には要らない．空列を含む語頭のない集合は空列だけからなり，そのとき和は $1$ だからである．

自己限定万能機械

定義 13.4.3（自己限定形と自己限定万能機械）. ビット列 $𝑑$ に対し， $1$ を $| 𝑑 |$ 個並べ， $0$ を一つ置き，そのあとに $𝑑$ をつないだビット列を $𝑑$ の 自己限定形 と呼ぶ（その長さは $2 | 𝑑 | + 1$ である）．ビット列 $𝑠$ に自然数を対応させる部分関数 $V$ を次のように定める． $𝑠$ の先頭から最初の $0$ が現れるまでの $1$ の個数を $𝑚$ ，その $0$ より後ろのビット列を $𝑑$ とする（ $𝑠$ に $0$ が現れないときは $𝑚 : = | 𝑠 |$ ， $𝑑$ を空列とする）． $𝑚 = | 𝑑 |$ のとき $V (𝑠) : = U (𝑑, 0)$ とし，そうでないとき $V (𝑠)$ は値を持たないとする． $V$ を 自己限定万能機械 と呼ぶ． $𝑥 \in ℕ$ に対し

𝐾 V (𝑥) : = m i n {| 𝑠 | : V (𝑠) = 𝑥}

と定める（ $𝑠$ はビット列の全体をわたる．そのようなビット列が一つも無いときは $+ \infty$ とする）．

形式化: 自己限定形 selfDelimit，機械 prefixUniversalEval，記述長 prefixComplexity (ソース)

本節の $𝐾 V$ は，機械 $V$ についての記述長である． $V$ の作り方を変えたときに $𝐾 V$ の値がどれだけ動くかについて，本書は何も述べない．本章が $𝐾$ につねに機械を添字として書くのは，このためでもある．

$V$ の読み方は，長さを先に書いておく，というだけのものである． $U$ に渡したいビット列 $𝑑$ があるとき，その長さを $1$ の個数で書き，区切りの $0$ を置いてから $𝑑$ を並べる．読む側は $1$ を数えて長さを知り，区切りのあとをちょうどその長さだけ読めばよいので，どこで読み終えるかが読んだ範囲だけで決まる．長さが合わないプログラムを捨てるのはそのためで，捨てておかないと，同じ $𝑑$ に対して前置きの長さの違うプログラムがいくつも値を持ってしまう．はじめに見た，プログラムが自分の終わりを自分で告げるという形が，ここで具体の姿をとる．自己限定という名前もそこから来ている．

$U$ と同じく， $V$ も定義 13.1.3 の意味の機械ではない．13.1 節が $U$ について述べたとおり，機械はビット列をそれが表す自然数を通してしか見ないのに対し， $V$ はビット列そのものを読むからである．いっぽう $V$ も計算の手続きで定まる． $1$ の並びを数えて長さを比べるところは有限回の繰り返しで，残りは $U$ を走らせるところだから，Church–Turing のテーゼより $V$ は部分計算可能である．

命題 13.4.4. $V$ が値を持つビット列は，どれもあるビット列の自己限定形（定義 13.4.3）である．とくに， $V$ が値を持つビット列の全体は定義 13.4.1 の意味で語頭のない集合であり，空列を含まない．

証明. $V (𝑠)$ が値を持つとし，定義 13.4.3 の $𝑚$ と $𝑑$ をとる． $𝑠$ に $0$ が現れないときは $𝑑$ が空列で $𝑚 = | 𝑠 |$ だから， $𝑚 = | 𝑑 | = 0$ は $𝑠$ が空列であることを意味する．ところが空列については $𝑑$ も空列で $V (𝑠) = U (𝑑, 0)$ となり，定義 13.1.4 より空列に対する $U$ は値を持たない．よって $𝑠$ には $0$ が現れ， $𝑠$ は $1$ を $𝑚$ 個並べ， $0$ を一つ置き，長さ $𝑚$ のビット列 $𝑑$ をつないだ形である．これは $𝑑$ の自己限定形にほかならない．

空列を含まないことは，いま見たとおりである．語頭のない集合であることを示す． $𝑠$ と $𝑡$ が $V$ で値を持ち， $𝑠$ が $𝑡$ の語頭だとする．前段より $𝑠$ はあるビット列 $𝑑$ の， $𝑡$ はあるビット列 $𝑒$ の自己限定形であり， $𝑠$ の先頭から最初の $0$ までの $1$ の個数は $| 𝑑 |$ ， $𝑡$ については $| 𝑒 |$ である． $| 𝑑 | < | 𝑒 |$ とすると， $1$ を $| 𝑑 |$ 個並べた直後の位置で， $𝑠$ のビットは $0$ であり， $𝑡$ のビットは $1$ である（ $𝑡$ の先頭 $| 𝑒 |$ ビットはすべて $1$ だからである）．この位置は $𝑠$ の中にある． $| 𝑠 | = 2 | 𝑑 | + 1$ が $| 𝑑 |$ より大きいからである．いっぽう $𝑠$ が $𝑡$ の語頭なら，この位置の二つのビットは一致しなければならず，矛盾する． $| 𝑑 | > | 𝑒 |$ としても， $1$ を $| 𝑒 |$ 個並べた直後の位置で同じ矛盾が出る．よって $| 𝑑 | = | 𝑒 |$ であり， $| 𝑠 | = 2 | 𝑑 | + 1 = | 𝑡 |$ である．長さの等しい語頭は列そのものだから $𝑠 = 𝑡$ である． $◼$

形式化: 自己限定形であること dom_imp_mem_range，語頭のない集合であること prefixUniversalEval_dom_prefixFree，空列を含まないこと prefixUniversalEval_nil_not_dom (ソース)

命題 13.4.5. $𝑥 \in ℕ$ とすると， $| 𝑠 | = 𝐾 V (𝑥)$ かつ $V (𝑠) = 𝑥$ を満たすビット列 $𝑠$ が存在する．

証明. 命題 13.1.5 を $𝑦 : = 0$ に当てると， $U (𝑑, 0) = 𝑥$ を満たすビット列 $𝑑$ がある． $𝑡$ を $𝑑$ の自己限定形とすると， $𝑡$ の先頭から最初の $0$ までの $1$ の個数は $| 𝑑 |$ ，その後ろは $𝑑$ だから，定義 13.4.3 より $V (𝑡) = U (𝑑, 0) = 𝑥$ である．よって集合 ${| 𝑠 | : V (𝑠) = 𝑥}$ は空でない自然数の集合であり，最小元をもつ．その最小元は $𝐾 V (𝑥)$ にほかならず，しかも $V (𝑠) = 𝑥$ を満たすあるビット列 $𝑠$ の長さだから，その $𝑠$ が求めるものである． $◼$

形式化: prefixComplexity_spec (ソース)

命題 13.4.6. $𝑥 \in ℕ$ とすると $𝐾 V (𝑥) = 2 𝐾 U (𝑥) + 1$ である．

証明. 上から抑える．命題 13.1.5 を $𝑦 : = 0$ に当てて， $| 𝑑 | = 𝐾 U (𝑥 ∣ 0) = 𝐾 U (𝑥)$ かつ $U (𝑑, 0) = 𝑥$ を満たすビット列 $𝑑$ をとる． $𝑠$ を $𝑑$ の自己限定形とすると，命題 13.4.5 の証明と同じ読み方で $V (𝑠) = 𝑥$ であり， $| 𝑠 | = 2 | 𝑑 | + 1 = 2 𝐾 U (𝑥) + 1$ だから，定義 13.4.3 の最小はこの値以下である．

下から抑える． $V (𝑠) = 𝑥$ とすると，命題 13.4.4 より $𝑠$ はあるビット列 $𝑑$ の自己限定形である．このとき定義 13.4.3 の $𝑚$ は $| 𝑑 |$ に等しいので $V (𝑠) = U (𝑑, 0)$ であり， $U (𝑑, 0) = 𝑥$ が従う．よって定義 13.1.4 の最小より $| 𝑑 | \geq 𝐾 U (𝑥)$ であり， $| 𝑠 | = 2 | 𝑑 | + 1 \geq 2 𝐾 U (𝑥) + 1$ である． $V (𝑠) = 𝑥$ を満たす $𝑠$ は任意だったから，その長さの最小である $𝐾 V (𝑥)$ も $2 𝐾 U (𝑥) + 1$ 以上である． $◼$

形式化上の注記. 命題 13.4.6 に対応する単独の宣言は無い．形式化は同じ等式を， $U$ に渡すビット列の長さの最小値について prefixComplexity_eq_two_mul_payloadComplexity_add_one (InformationTheory/Shannon/Kolmogorov/Levin.lean) として持っている．そこに現れる payloadComplexity は，本文の $𝐾 U (\cdot ∣ 0)$ にあたる量を $V$ の側から定め直したもので，二つが一致することを述べる宣言は無い．定義を開けば同じ部分関数についての最小だが，その等式には名前が与えられていないからである．

命題 13.4.6 は，本書の $𝐾 V$ が $𝐾 U$ から完全に決まることを言っている．すなわち記述長の側では，機械を取り替えたことで新しく得たものは何も無い．得たものは重みの側にある．命題 13.4.4 のとおり $V$ が値を持つプログラムの全体は語頭のない集合なので，補題 13.4.2 よりそれらの重みの総和は $1$ を超えない．このあと定義 13.4.8 で入れる $𝑃 V$ を確率として読めるのは，この一点による． $V$ を置いたのはそのためである．

等式が成り立つのは定義 13.4.3 で機械を一つに固定したからであって，値を持つプログラムの全体が語頭のない集合であるような機械の一般について成り立つ話ではない．情報理論の文献が語頭複雑性と呼ぶ量は，そのような機械のうち，どの機械の記述も定数の払いで真似できるものをとって定めるもので，機械の取り方に定数のずれが残るぶん，命題 13.4.6 のような等式を主張として持たない．読者が本書の外で語頭複雑性を引くときは，本書の $𝐾 V$ とは別の量である．

定理 13.4.7（係数 $2$ の不変性）. $M$ を定義 13.1.3 の意味の機械とすると，定数 $𝑏 \in ℕ$ があって，すべての $𝑥 \in ℕ$ とすべてのビット列 $𝑠$ について， $M (𝑠, 0) = 𝑥$ ならば $𝐾 V (𝑥) \leq 2 | 𝑠 | + 𝑏$ が成り立つ．

証明. 定理 13.1.7 をこの $M$ に当てて定数 $𝑏 0 \in ℕ$ をとり， $𝑏 : = 2 𝑏 0 + 1$ と置く． $𝑥 \in ℕ$ とビット列 $𝑠$ が $M (𝑠, 0) = 𝑥$ を満たすとすると，定理 13.1.7 より $𝐾 U (𝑥) = 𝐾 U (𝑥 ∣ 0) \leq | 𝑠 | + 𝑏 0$ である．命題 13.4.6 と合わせて

𝐾 V (𝑥) = 2 𝐾 U (𝑥) + 1 \leq 2 | 𝑠 | + 2 𝑏 0 + 1 = 2 | 𝑠 | + 𝑏

である． $◼$

形式化: prefix_invariance (ソース)

定理 13.4.7 と定理 13.1.7 の違いは係数 $2$ だけである．定理 13.1.7 の右辺は $| 𝑠 |$ に定数を足したものだったので， $| 𝑠 |$ が大きくなるほど払いは相対的に軽くなった．定理 13.4.7 の右辺は $| 𝑠 |$ の $2$ 倍なので，そうはならない．ただし，この $2$ を定数に落とした形が成り立たない，とまでは定理 13.4.7 からは出ない．定理 13.4.7 は一つの上界を与えるだけで，これより良い上界が無いことは言っていないからである．

万能確率

定義 13.4.8（万能確率）. $𝑥 \in ℕ$ に対し

𝑃 V (𝑥) : = \sum 𝑠 : V (𝑠) = 𝑥 2 - | 𝑠 |

と定め（ $𝑠$ は $V (𝑠) = 𝑥$ を満たすビット列の全体をわたる）， $𝑥$ の 万能確率 と呼ぶ．

形式化: universalProb (ソース)

$𝑃 V$ はつねに $V$ を添字にとり，引数を一つとる．第10章から第12章までが裸の $𝑃$ で書いてきた分布とは別の量であり，13.3 節が $𝑝 𝑛$ と書いた積分布とも関係がない． $𝑃 V (𝑥)$ が測っているのは，でたらめに投げたビット列を $V$ に読ませたとき， $𝑥$ が出てくる重みである． $𝑥$ を出すプログラムが短いほど，そのプログラムの重み $2 - | 𝑠 |$ は大きい．すなわち $𝑃 V$ は，短く書ける対象ほど大きな値をとる．次の定理 13.4.10 が言うのは，この対応が定数倍の範囲で逆向きにも成り立つことである．

命題 13.4.9. $𝑥 \in ℕ$ とすると $2 - 𝐾 V (𝑥) \leq 𝑃 V (𝑥) \leq 1$ である．とくに $𝑃 V (𝑥) > 0$ である．

証明. 左の不等式を示す．命題 13.4.5 より $| 𝑠 | = 𝐾 V (𝑥)$ かつ $V (𝑠) = 𝑥$ を満たすビット列 $𝑠$ がある．定義 13.4.8 の和はこの $𝑠$ の項を含み，項はどれも非負だから，和はこの項の値 $2 - 𝐾 V (𝑥)$ 以上である．

右の不等式を示す． $V (𝑠) = 𝑥$ を満たすビット列の全体を $𝑆$ と置くと， $𝑆$ は $V$ が値を持つビット列の全体の部分集合である．命題 13.4.4 より後者は空列を含まない語頭のない集合であり，その部分集合も同じ条件を満たすから，補題 13.4.2 を $𝑆$ に当てて $𝑃 V (𝑥) \leq 1$ を得る．最後に， $2 - 𝐾 V (𝑥)$ は正だから $𝑃 V (𝑥) > 0$ である． $◼$

形式化: 左の不等式 universalProb_ge_two_pow_neg_prefixComplexity，右の不等式 universalProb_le_one (ソース)

形式化上の注記. 正値性に対応する単独の宣言は無い．左の不等式に紐付けた宣言と， $2 - 𝐾 V (𝑥)$ が正であることを合わせれば得られる．

定理 13.4.10（記述長と万能確率）. $𝑥 \in ℕ$ とすると

- l o g 2 𝑃 V (𝑥) \leq 𝐾 V (𝑥) \leq 2 (- l o g 2 𝑃 V (𝑥)) + 1

が成り立つ．

証明. 命題 13.4.9 より $𝑃 V (𝑥) > 0$ だから， $l o g 2 𝑃 V (𝑥)$ は定まる．

左の不等式を示す．命題 13.4.9 の左の不等式に補題 8.2.5 を当てると $- 𝐾 V (𝑥) \leq l o g 2 𝑃 V (𝑥)$ であり，両辺の符号を変えて $- l o g 2 𝑃 V (𝑥) \leq 𝐾 V (𝑥)$ を得る．

右の不等式の準備として $𝑃 V (𝑥) \leq 2 - 𝐾 U (𝑥)$ を示す． $V (𝑠) = 𝑥$ とすると，命題 13.4.6 の証明で見たとおり $𝑠$ はあるビット列 $𝑑$ の自己限定形で， $U (𝑑, 0) = 𝑥$ かつ $| 𝑑 | \geq 𝐾 U (𝑥)$ である．そこで， $1$ を $| 𝑑 | - 𝐾 U (𝑥)$ 個並べ， $0$ を一つ置き，そのあとに $𝑑$ をつないだビット列を $˜ 𝑠$ と書く． $𝑠$ の前置きの $1$ を $𝐾 U (𝑥)$ 個だけ剥がした列である．その長さは

| ˜ 𝑠 | = (| 𝑑 | - 𝐾 U (𝑥)) + 1 + | 𝑑 | = | 𝑠 | - 𝐾 U (𝑥)

である．剥がすのは， $𝑥$ を出すプログラムの重みの和を補題 13.4.2 に持ち込むためである． $V$ が値を持つビット列そのものに補題 13.4.2 を当てても $1$ 以下しか出ないが，長さをどれも $𝐾 U (𝑥)$ だけ縮めてから当てれば，縮めたぶんが $2 - 𝐾 U (𝑥)$ の因子として残る．なお，長さ $ℓ$ の $𝑑$ の本数を $2 ℓ$ で抑えて長さごとに足しても同じ上界は出る．ここでこの形をとるのは，次節の例 13.5.9 が上からの評価に同じ剥がし方を使うからである．

対応 $𝑠 \mapsto ˜ 𝑠$ は単射である．というのも $˜ 𝑠$ の最初の $0$ より後ろが $𝑑$ で， $𝑠$ は $𝑑$ の自己限定形として $𝑑$ から決まるからである．また $˜ 𝑠$ の全体は空列を含まない語頭のない集合である． $˜ 𝑠$ が $˜ 𝑡$ の語頭だとして， $𝑡$ に対応するビット列を $𝑒$ と書く． $˜ 𝑠$ の先頭には $1$ が $| 𝑑 | - 𝐾 U (𝑥)$ 個並んでその直後が $0$ であり， $˜ 𝑡$ の先頭には $1$ が $| 𝑒 | - 𝐾 U (𝑥)$ 個並ぶ． $| 𝑑 | < | 𝑒 |$ とすると， $1$ を $| 𝑑 | - 𝐾 U (𝑥)$ 個並べた直後の位置で， $˜ 𝑠$ のビットは $0$ であり， $˜ 𝑡$ のビットは $1$ である．この位置は $˜ 𝑠$ の中にある． $| ˜ 𝑠 | = 2 | 𝑑 | + 1 - 𝐾 U (𝑥)$ が $| 𝑑 | - 𝐾 U (𝑥)$ より大きいからである．いっぽう $˜ 𝑠$ が $˜ 𝑡$ の語頭なら，この位置の二つのビットは一致しなければならず，矛盾する． $| 𝑑 | > | 𝑒 |$ としても， $1$ を $| 𝑒 | - 𝐾 U (𝑥)$ 個並べた直後の位置で同じ矛盾が出る．よって $| 𝑑 | = | 𝑒 |$ であり， $| ˜ 𝑠 | = | ˜ 𝑡 |$ となるから，長さの等しい語頭は列そのものだから $˜ 𝑠 = ˜ 𝑡$ である．空列でないことは， $˜ 𝑠$ が $0$ を含むことによる．

$V (𝑠) = 𝑥$ を満たす $𝑠$ の有限個の集まりを $𝐹$ とすると，いま見たことと補題 13.4.2 から

\sum 𝑠 \in 𝐹 2 - | 𝑠 | = 2 - 𝐾 U (𝑥) \sum 𝑠 \in 𝐹 2 - | ˜ 𝑠 | \leq 2 - 𝐾 U (𝑥)

である．和を有限部分和の上限として定めたことから， $𝑃 V (𝑥) \leq 2 - 𝐾 U (𝑥)$ である．

右の不等式を示す．いま示した不等式に補題 8.2.5 を当てると $l o g 2 𝑃 V (𝑥) \leq - 𝐾 U (𝑥)$ ，すなわち $𝐾 U (𝑥) \leq - l o g 2 𝑃 V (𝑥)$ である．命題 13.4.6 と合わせて

𝐾 V (𝑥) = 2 𝐾 U (𝑥) + 1 \leq 2 (- l o g 2 𝑃 V (𝑥)) + 1

を得る． $◼$

形式化: 左の不等式 neg_logb_universalProb_le_prefixComplexity (ソース)，右の不等式 prefixComplexity_le_two_mul_neg_logb_universalProb (ソース)

定理 13.4.10 は，記述の短さと重みの大きさが同じことを測っているという主張である．左の不等式は， $𝑥$ を出すプログラムが一本でも短ければ重みが大きいという当たり前の向きで，最短の一本だけを数えて出る．右の不等式が言っているのは逆向きで，重みが大きければ短いプログラムが実際にあるということである．こちらは短いプログラムが一本もない場合を排除しなければならないので，長いプログラムがいくら集まっても重みが稼げないこと，すなわち補題 13.4.2 の数え上げが要る．挟み撃ちの幅は係数 $2$ で， $- l o g 2 𝑃 V (𝑥)$ が大きいほど広がる．

この幅は，一方についての主張をもう一方へ移すときに効く． $𝐾 U$ の値を返す手続きが無いことは定理 13.2.3 で見たので，命題 13.4.6 より $𝐾 V$ についても同じことが言える．ところが定理 13.4.10 は幅のある挟み撃ちなので， $𝑃 V$ の値についても同じだ，とはここから出ない．本書は $𝑃 V$ の計算可能性を述べない．

この形の主張は Levin の符号化定理と呼ばれる．文献の主張は，値を持つプログラムの全体が語頭のない集合であるような機械のうち，どの機械の記述も定数の払いで真似できるものについてのもので，記述長と $- l o g 2$ をとった重みが定数の差で一致するという，係数のない鋭い形をしている．本書が示すのは定理 13.4.10 の係数 $2$ の挟み撃ちまでであり，文献の形は示さない．形式化もされていない．

命題 13.4.9 の左の不等式は最短の一本だけを見ており，和はまだ効いていない．和が効く例を一つ見ておく．

例 13.4.11（ $0$ の万能確率）. $𝐾 V (0) = 3$ であり， $𝑃 V (0) \geq 1 / 6 > 1 / 8 = 2 - 𝐾 V (0)$ である．とくに命題 13.4.9 の左の不等式は等号ではない．

証明. $𝐾 V (0)$ を求める．空列に対して $U$ は定義 13.1.4 より値を持たないから $𝐾 U (0) \geq 1$ である．いっぽう $0$ の一文字からなるビット列 $𝑑$ をとると， $𝑑$ の先頭のビットは $0$ でその後ろは空列だから，定義 13.1.4 より $U (𝑑, 0)$ は空列が表す自然数，すなわち $0$ である．よって $𝐾 U (0) = 1$ であり，命題 13.4.6 より $𝐾 V (0) = 2 \times 1 + 1 = 3$ である．

下から抑える． $𝑗 \geq 1$ に対し， $𝑑 𝑗$ を $0$ を $𝑗$ 個並べたビット列， $𝑠 𝑗$ を $𝑑 𝑗$ の自己限定形（定義 13.4.3）とする． $𝑑 𝑗$ の先頭のビットは $0$ で，その後ろは $0$ を $𝑗 - 1$ 個並べた列だから，定義 13.1.4 より $U (𝑑 𝑗, 0)$ はその列が表す自然数，すなわち $0$ である．よって定義 13.4.3 より $V (𝑠 𝑗) = 0$ であり，その長さは $| 𝑠 𝑗 | = 2 𝑗 + 1$ である．長さが違うから $𝑠 1, 𝑠 2, \dots$ は相異なる．

$𝐽 \geq 1$ を任意にとる． $𝑗 = 1, \dots, 𝐽$ の $𝑠 𝑗$ は相異なる有限個のビット列で，どれも $V$ の値が $0$ だから，それらの重みの和は定義 13.4.8 の和の有限部分和である．その値は

𝐽 \sum 𝑗 = 1 2 - (2 𝑗 + 1) = 12 𝐽 \sum 𝑗 = 1 4 - 𝑗 = 16 (1 - 4 - 𝐽)

である．和を有限部分和の上限として定めたことから $𝑃 V (0)$ はこの値以上であり， $𝐽$ を大きくすると右辺は $1 / 6$ に近づくから， $𝑃 V (0) \geq 1 / 6$ である．最後に $1 / 6 > 1 / 8 = 2 - 3$ である． $◼$

証明が数えたプログラムは， $1$ を $𝑗$ 個， $0$ を一つ， $0$ を $𝑗$ 個と並べたもので， $𝑗 \geq 1$ ごとに一本ずつある． $U$ に渡る部分はどれも「これから書くとおりに書け」という同じ指示で，違うのは後ろに並ぶ $0$ の個数だけである．最短の一本 $𝑠 1 = 100$ が重み $1 / 8$ を持ち，残りが合わせて $1 / 24$ を足す． $𝑃 V$ が最短の記述だけでなく記述の本数も見ていることが，ここで初めて数として出る．次節の例 13.5.9 の下からの評価は，同じ数え方を， $U$ に渡る部分が $0$ で始まるプログラムの全体に広げる．

次節は，この機械について二つの計算不可能性を示す．一つは $𝐾 V$ の値を返す手続きが無いこと，もう一つは $V$ が値を持つかどうかを答える手続きが無いことである．そのうえで，値を持つプログラム全体の重みを一つの実数にまとめ，その実数もまた計算できないことを見る．

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