13.1 記述の長さと万能機械

第2章から第12章まで，系列がどれだけ縮むかはつねに分布を通して測ってきた．第2章の漸近等分配性は情報源の分布からエントロピーを取り出し，第4章の符号長の下界も，第12章の冗長度も，分布があってはじめて書ける量である．ところが実際に手元にあるのは，分布ではなく一本の系列である． $0$ を $1000$ 個並べた系列と，コインを $1000$ 回投げて得た系列を並べれば，前者のほうが単純だと言いたくなる．どちらも同じ一様分布から同じ確率で出うるのだから，この単純さは分布では説明できない．

本章は，一つの対象そのものに複雑性の尺度を与える．考え方は素朴で，その対象を書き出す手続きのうち，いちばん短いものの長さを複雑性とする． $0$ を $1000$ 個並べた系列は「 $0$ を $1000$ 回書け」という短い手続きで書き出せる．コイン投げの結果にそのような手続きがあるとは限らず，短い手続きを持つ対象がどれだけあるかは 13.2 節で数える．手続きを長さで測るには，手続きを読んで実行する側の規約を一つ決めなければならない．規約を取り替えれば長さも変わるので，このままでは対象だけで決まる量にならない．本節は規約を一つ固定する作り方を与え，そう固定して測ると，どの規約で測るより定数のぶんしか損をしないこと（定理 13.1.7 と系 13.1.8）までを示す．

本章では対数の底を $2$ にとる．測るのはビット列の長さであり， $2 𝑘$ の形の量を数えるので，指数と対数の底をそろえておくと式が読みやすい．底を明示するため，以下では $l o g 2$ と書く．エントロピー $𝐻$ （定義 1.1.1）と二値エントロピー $𝐻 𝑏$ （例 1.1.2）もこの底で測り，単位はビットである．対数が狭義単調増加であること（補題 8.2.5）も本章を通して使う．

計算の手続き

本章が組み立てるものは，どれも計算の手続きで書ける対応である．その言葉を，本書は定義しない．定義するには計算モデル（Turing 機械や部分再帰関数）を一つ選んで書き下す必要があり，それは本書の主題ではないからである．そのかわり，以下で手続きと呼ぶものの姿を先に述べておく．有限個の場合分けと，有限回の繰り返しと，止まるとは限らない探索とを組み合わせて書き下せるもの，というのがそれである．最後の一つがあるために，手続きは引数によっては答えを返さないことがある．たとえば，自然数 $𝑧$ を受け取って $𝑧, 𝑧 + 1, 𝑧 + 2, \dots$ の順に調べ， $𝑧$ より小さい数が見つかったところで止めてその数を返す，という手続きは，どの $𝑧$ についても止まらないので，どの引数でも答えを返さない．答えが返らない理由はつねに，手続きが止まらないことにある．

定義 13.1.1（部分計算可能な部分関数と計算可能な関数）. 自然数をいくつか受け取って自然数を返す部分関数のうち，計算の手続きで定まるものを 部分計算可能 と呼ぶ．部分計算可能な部分関数のうち，すべての引数で値を持つものを 計算可能 と呼ぶ．

部分関数と書いたのは，いま見たとおり手続きが引数によっては答えを返さないからである．値を持たない引数があってよい，という一点だけが，関数との違いである．

そのうえで，計算可能性の理論から二つ借りる．一つめを 部分計算可能関数の番号づけと万能定理 と呼ぶ（Kleene）．自然数の対から自然数への部分関数の全体は非可算だが，手続きは有限個の文字を並べて書き下せるものなので，手続きで定まる部分関数は，書き下し方の全体と同じく高々可算個しかない．番号を与えられる余地があるのはそのためで，借りるのは次の主張である．自然数の対から自然数への部分計算可能な部分関数の全体に番号 $0, 1, 2, \dots$ を与える対応 $𝑖 \mapsto M 𝑖$ があり，しかも三つ組 $(𝑖, 𝑧, 𝑦)$ に $M 𝑖 (𝑧, 𝑦)$ を対応させる部分関数もまた部分計算可能である．

依存範囲は本章の全節である．本章が固定する二つの機械の定め方がこの枠組みの上にあるから，本章のどの主張もこれを認めたうえでの主張である．ただし直に当てるのは定義 13.1.4 の万能機械 $U$ と定理 13.1.7 の二つで，13.4 節以降はそれらを経由してのみ依存する．後半の，三つ組を受け取る部分関数もまた部分計算可能だという主張を借りるのは， $U$ 自身が計算の手続きで定まることを言うためで，当てるのは定義 13.1.4 の直後である． $U$ を実際に走らせる手続きを組み立てる 13.4 節から 13.6 節までは，その一事に乗っている．

二つめを Church–Turing のテーゼ と呼ぶ．いま述べた姿で書き下せる対応，すなわち有限個の場合分けと有限回の繰り返しと止まるとは限らない探索とで書ける対応は定義 13.1.1 の意味で部分計算可能であり，そのうち必ず停止して答えを返すものは計算可能である，という主張である．当てるのは本章が書き下す手続きで，本章のどの節にも一つ以上ある．ほかの主張はそれらを経由してのみこれに依存する．これは定理ではない．「計算の手続き」という言葉を定義 13.1.1 のクラスで代表させるという約束であり，その言葉を定義しないと決めた以上，証明できる種類の主張ではない．

自然数とビット列

記述はビット列で書き，その長さを測る．いっぽう定義 13.1.1 が相手にしているのは自然数を受け取る部分関数だから，二つを行き来する対応を決めておかなければならない．

定義 13.1.2（自然数とビット列の対応）. 自然数 $𝑥$ には二進表示のビット列を対応させ，そのビット数を $| 𝑥 |$ と書く（ $0$ には空列を対応させるので $| 0 | = 0$ である）．逆に，自然数を引数にとる関数にビット列 $𝑠$ を渡すときは， $𝑠$ を二進表示として読んだ値を渡し，これを $𝑠$ が 表す自然数 と呼ぶ（空列が表す自然数は $0$ とする）．どの自然数についても，その二進表示が表す自然数はもとの自然数に等しい．ビット列 $𝑠$ については， $𝑠$ が空列であるか $𝑠$ の先頭のビットが $1$ であるとき， $𝑠$ が表す自然数の二進表示は $𝑠$ に等しい．

たとえば $| 1 | = 1$ であり， $𝑛 \geq 1$ について $| 2 𝑛 | = 𝑛 + 1$ である．二つの向きは対称ではない．戻らないのは先頭に $0$ の並ぶビット列で，たとえば $01$ が表す自然数は $1$ ，その二進表示は $1$ であって $01$ には戻らない．先頭の $0$ が消えるというこの非対称は，13.4 節で機械を取り替える理由になる．二進表示として読ませる列の先頭に $0$ を足しても表す自然数は変わらないので，同じ値を出す指示がいくらでも長く作れてしまい，そこで邪魔になるからである．集合 $X$ の要素数を書く $| X |$ と字面が重なるが，そちらは引数が集合である．

機械と記述長

定義 13.1.3（機械と記述長）. 自然数の対から自然数への部分計算可能な部分関数を機械と呼ぶ．機械 $M$ にビット列 $𝑠$ を渡すとは， $𝑠$ が表す自然数を第 $1$ 引数に与えることをいい，その値を $M (𝑠, 𝑦)$ と書く． $M (𝑠, 𝑦) = 𝑥$ とは， $M$ がその引数で値を持ち，その値が $𝑥$ であることをいう．機械 $M$ と $𝑥, 𝑦 \in ℕ$ に対し

𝐾 M (𝑥 ∣ 𝑦) : = m i n {| 𝑠 | : M (𝑠, 𝑦) = 𝑥}

と定め（ $𝑠$ はビット列の全体をわたる）， $M$ についての 記述長 と呼ぶ．そのようなビット列が一つも無いときは $𝐾 M (𝑥 ∣ 𝑦) : = + \infty$ と定める．

$𝐾$ には，つねに機械を添字として書く．既刊の章は裸の $𝐾$ を，第4章 4.3 節と 4.5 節，第12章 12.3 節では Kraft の不等式の左辺として，第5章 5.3 節ではオッズの逆数の総和として，第6章 6.6 節では証明の中の定数として使っている．本章の $𝐾$ はつねに機械を添字にとり，引数もとるので，裸の $𝐾$ は本章に現れない．

形式化上の注記（本節共通）. 一般の機械についての記述長，すなわち定義 13.1.3 の $𝐾 M$ に名前を与えた宣言は無く，その最小を使って書いた系 13.1.8 に対応する単独の宣言も無い．機械を取り替えたときの評価は invariance (InformationTheory/Shannon/Kolmogorov/Invariance.lean) が，最小をとらずに記述そのものの長さを直に扱う形で述べている．

読み下しておく． $𝑠$ は $M$ に渡す指示で， $𝑦$ は最初から手元にある知識である． $𝐾 M (𝑥 ∣ 𝑦)$ は， $𝑦$ を知ったうえで $𝑥$ を $M$ に書き出させる指示のうち，いちばん短いもののビット数にほかならない．機械は定義 13.1.3 のとおり，ビット列を定義 13.1.2 の表す自然数を通してしか見ない．先頭に $0$ を並べても値は変わらず長さだけが増えるから，この最小は， $M (𝑧, 𝑦) = 𝑥$ を満たす自然数 $𝑧$ の二進表示の長さの最小に等しい．それでも指示をビット列で書いて測るのは，このあとの $U$ がビット列そのものを読むからで，同じ形の式で二つを比べられるようにするためである．この量は $M$ を取り替えれば大きくも小さくもなる．極端な場合を見ておくと，引数によらず $𝑥 0$ を返す機械をとれば，空列を渡すだけで $𝑥 0$ が出るので $𝐾 M (𝑥 0 ∣ 𝑦) = 0$ である．だから記述長そのものは対象だけで決まる量ではなく，機械と対象の組についての量である．本節の残りは，機械を一つ固定する作り方を与え，その機械で測ると，どの機械で測るより定数のぶんしか損をしないことを示す．

万能機械

指示の出し方を二つ用意し，先頭のビットで見分けることにする．一つめは「これから書くとおりに書け」で，先頭に $0$ を置き，その後ろに $𝑥$ の二進表示をそのまま並べる．二つめは「番号 $𝑖$ の機械を，これから書く指示で走らせろ」で，先頭の $1$ に続けて番号 $𝑖$ を $1$ の個数で書き，区切りの $0$ を置いてから指示を並べる．一つめは誰にでも使えるかわりに $𝑥$ の長さだけ払う．二つめは， $𝑥$ に見合った機械があれば短く済むかわりに，その機械の番号を書く分だけ余計に払う．この見分け方で，次の機械を定める．

定義 13.1.4（万能機械とコルモゴロフ複雑性）. ビット列 $𝑠$ と $𝑦 \in ℕ$ の対に自然数を対応させる部分関数 $U$ を， $𝑠$ の先頭のビットで場合を分けて次のように定める（ $𝑠$ が空列のとき， $U (𝑠, 𝑦)$ は値を持たない）．

$𝑠$ の先頭のビットが $0$ のとき，その後ろのビット列を $𝑑$ として， $U (𝑠, 𝑦)$ を $𝑑$ が表す自然数とする．

$𝑠$ の先頭のビットが $1$ のとき， $2$ 番目のビットから最初の $0$ が現れるまでの $1$ の個数を $𝑖$ ，その $0$ より後ろのビット列を $𝑑$ とし（ $2$ 番目以降に $0$ が現れないときは $2$ 番目以降のビットの個数を $𝑖$ ， $𝑑$ を空列とする）， $U (𝑠, 𝑦) : = M 𝑖 (𝑑, 𝑦)$ とする．ここで $M 𝑖$ は，部分計算可能関数の番号づけと万能定理が与える番号 $𝑖$ の部分関数である．

この $U$ を 万能機械 と呼ぶ． $𝑥, 𝑦 \in ℕ$ に対し

𝐾 U (𝑥 ∣ 𝑦) : = m i n {| 𝑠 | : U (𝑠, 𝑦) = 𝑥}

と定め（ $𝑠$ はビット列の全体をわたる）， $𝑦$ を知ったうえでの $𝑥$ の コルモゴロフ複雑性 と呼ぶ．また，第 $2$ 引数に何も渡さないことの代用として $0$ を置き， $𝐾 U (𝑥) : = 𝐾 U (𝑥 ∣ 0)$ と書く．

形式化: 万能機械 universalEval，コルモゴロフ複雑性 condComplexity と complexity (ソース)

$U$ は定義 13.1.3 の意味の機械ではない．機械はビット列を，それが表す自然数を通してしか見ないのに対し， $U$ はビット列そのものを読み，先頭のビットで場合を分けるからである．では，なぜ機械のほうをはじめからビット列の上で定めなかったのか．借りた番号づけが自然数の部分関数に番号を与えるものだからである．番号 $𝑖$ の相手 $M 𝑖$ が自然数を読む以上，定義 13.1.3 の機械もそれに合わせるほかない． $U$ が機械でないことで困ることは無い．以下で $U$ について使うのは記述長の式と， $U$ が計算の手続きで定まるという一事だけで，どちらも定義 13.1.3 の枠に入っていることを要求しないからである．

記述長は定義 13.1.3 と同じ形の式で定まるので， $𝐾$ の添字が機械の名前か $U$ かで読み分ければよい． $U$ を万能と呼ぶのは，どの機械の記述も定数の払いで真似できるからであって（定理 13.1.7）， $U$ が機械の一つだからではない．その $U$ 自身も計算の手続きで定まる．先頭のビットを読んで場合を分け， $1$ の並びを数えるところは Church–Turing のテーゼが与え，番号 $𝑖$ の部分関数を走らせるところは部分計算可能関数の番号づけと万能定理の後半が与える．

形式化上の注記（本章共通）. 本文は，いま $U$ について見たように，書き下した手続きが計算の手続きで定まることを Church–Turing のテーゼで認めて先へ進む．形式化の側は，そのうちのいくつかについて部分計算可能であることを証明している．自己限定万能機械そのものは prefixUniversalEval_partrec (InformationTheory/Shannon/Kolmogorov/PrefixComputability.lean)，その機械を手数の予算をつけて走らせる手続きは prefixEvaln_primrec (InformationTheory/Shannon/Kolmogorov/OmegaNoncomputable.lean)，型と型類から系列を復元する手続きは typeDecoder_partrec (InformationTheory/Shannon/Kolmogorov/EntropyRateUpper.lean)，二部記述から対象を復元する手続きは twoPartUnpack_partrec と listIndexDecoder_partrec，一点集合の符号を求める手続きは singletonCode_partrec (InformationTheory/Shannon/Kolmogorov/SufficientStatistic.lean) である． $U$ そのものについての宣言は無い．prefixUniversalEval_partrec が扱うのは， $U$ と同じ場合分けを第 $2$ 引数を $0$ に固定して書き直した部分関数である．

二つの出し方を式にするのは命題 13.1.6 と定理 13.1.7 で，その前に， $𝐾 U$ を定める最小が実際に達成されることを見ておく．

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

証明. $𝑡$ を， $0$ の後ろに $𝑥$ の二進表示をつないだビット列とする． $𝑡$ の先頭のビットは $0$ で，その後ろは $𝑥$ の二進表示だから，定義 13.1.4 より $U (𝑡, 𝑦)$ は $𝑥$ の二進表示が表す自然数，すなわち $𝑥$ である．よって集合 ${| 𝑠 | : U (𝑠, 𝑦) = 𝑥}$ は空でない自然数の集合であり，最小元をもつ．その最小元は $𝐾 U (𝑥 ∣ 𝑦)$ にほかならず，しかも $U (𝑠, 𝑦) = 𝑥$ を満たすあるビット列 $𝑠$ の長さだから，その $𝑠$ が求めるものである． $◼$

形式化: condComplexity_spec (ソース)

命題 13.1.6. $𝑥, 𝑦 \in ℕ$ とすると $𝐾 U (𝑥 ∣ 𝑦) \leq | 𝑥 | + 1$ である．

証明. $𝑡$ を， $0$ の後ろに $𝑥$ の二進表示をつないだビット列とすると，定義 13.1.4 より $U (𝑡, 𝑦) = 𝑥$ である． $𝑡$ の長さは $𝑥$ の二進表示のビット数より $1$ 大きいから $| 𝑡 | = | 𝑥 | + 1$ であり，定義 13.1.4 の最小はこの値以下である． $◼$

形式化: condComplexity_le_natLen_add_one (ソース)

命題 13.1.6 は，どの自然数も，その二進表示の前に $1$ ビットを添えるだけで書き出せることを言っているにすぎない．どんなに複雑な対象でも，複雑性はそれを書き下す長さに $1$ を足した値を超えない，という当たり前の上界である．おもしろいのはここから先で，機械を工夫すればこの上界をどれだけ下回れるか，そして工夫の余地がどこで尽きるかである．

不変性定理

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

証明. 部分計算可能関数の番号づけと万能定理より， $M = M 𝑖$ となる番号 $𝑖$ がある． $𝑏 : = 𝑖 + 2$ とおく．

$𝑥, 𝑦 \in ℕ$ とビット列 $𝑠$ が $M (𝑠, 𝑦) = 𝑥$ を満たすとする． $𝑡$ を， $1$ を $𝑖 + 1$ 個並べ，次に $0$ を置き，最後に $𝑠$ をつないだビット列とする． $𝑡$ の先頭のビットは $1$ で， $2$ 番目のビットから最初の $0$ が現れるまでの $1$ の個数は $𝑖$ ，その $0$ より後ろは $𝑠$ だから，定義 13.1.4 の先頭が $1$ の場合に当たって $U (𝑡, 𝑦) = M 𝑖 (𝑠, 𝑦) = 𝑥$ である． $𝑡$ の長さは $(𝑖 + 1) + 1 + | 𝑠 | = | 𝑠 | + 𝑏$ だから，定義 13.1.4 の最小はこの値以下である． $◼$

形式化: invariance (ソース)

系 13.1.8. $M$ を機械とすると，定数 $𝑏 \in ℕ$ があって，すべての $𝑥, 𝑦 \in ℕ$ について $𝐾 U (𝑥 ∣ 𝑦) \leq 𝐾 M (𝑥 ∣ 𝑦) + 𝑏$ である．

証明. 定理 13.1.7 の定数 $𝑏$ をとり， $𝑥, 𝑦 \in ℕ$ とする． $𝐾 M (𝑥 ∣ 𝑦) = + \infty$ のときは不等式が成り立つ．そうでないときは，定義 13.1.3 の最小をとる集合が空でないので， $M (𝑠, 𝑦) = 𝑥$ かつ $| 𝑠 | = 𝐾 M (𝑥 ∣ 𝑦)$ を満たすビット列 $𝑠$ がある（自然数の空でない部分集合は最小元をもつ）．定理 13.1.7 をこの $𝑠$ に当てると $𝐾 U (𝑥 ∣ 𝑦) \leq | 𝑠 | + 𝑏 = 𝐾 M (𝑥 ∣ 𝑦) + 𝑏$ である． $◼$

系 13.1.8 が，本節のはじめに述べた問いへの答えである．機械をどう選び直しても， $𝐾 U$ が $𝐾 M$ より本質的に大きくなることはない．ずれは $𝑏$ という定数までで， $𝑏$ は $𝑥$ にも $𝑦$ にも依らず， $M$ の番号だけで決まる．したがって， $U$ を固定して測ることは，どの機械で測るより定数のぶんしか損をしない．コルモゴロフ複雑性が対象の量として意味を持つのは，この一点による．

抑えているのは片側だけであることに注意したい．逆に $𝐾 M$ を $𝐾 U$ で抑えることは，機械によってはできない（ $𝑥$ をけっして出力しない機械では定義 13.1.3 より $𝐾 M (𝑥 ∣ 𝑦) = + \infty$ である）．機械の選び方に左右されないと言えるのはこの片側までで，別の番号づけから同じ作り方で組み立てた機械とのあいだで $𝐾 U$ の値がどれだけ違いうるかについて，本書は何も述べない．一つの $𝑥$ についての $𝐾 U (𝑥)$ の値そのものも，定義 13.1.4 が固定した番号づけに依って決まる．本章が $𝐾$ につねに機械を添字として書くのは，このためである．

例 13.1.9（ $2$ の冪）. 定数 $𝑏 \in ℕ$ があって，すべての $𝑛 \geq 1$ について次の二つが成り立つ．第 $1$ に $| 2 𝑛 | = 𝑛 + 1$ であり $𝐾 U (2 𝑛) \leq 𝑛 + 2$ である．第 $2$ に $𝐾 U (2 𝑛) \leq | 𝑛 | + 𝑏$ である．

証明. $2 𝑛$ の二進表示は $1$ の後ろに $0$ を $𝑛$ 個並べたものだから $| 2 𝑛 | = 𝑛 + 1$ であり，命題 13.1.6 を $𝑥 : = 2 𝑛$ ， $𝑦 : = 0$ に当てて第 $1$ の主張を得る．

第 $2$ の主張に移る． $M (𝑧, 𝑦') : = 2 𝑧$ （第 $2$ 引数は使わない）と定めると， $𝑧$ から $2 𝑧$ を求める手続きは有限回の繰り返しで書けて必ず停止するから，Church–Turing のテーゼより $M$ は計算可能であり，とくに定義 13.1.3 の意味で機械である．定理 13.1.7 をこの $M$ に当てて定数 $𝑏$ をとる． $𝑛 \geq 1$ とし， $𝑠$ を $𝑛$ の二進表示のビット列とすると， $𝑠$ が表す自然数は $𝑛$ だから $M (𝑠, 0) = 2 𝑛$ であり， $𝐾 U (2 𝑛) = 𝐾 U (2 𝑛 ∣ 0) \leq | 𝑠 | + 𝑏 = | 𝑛 | + 𝑏$ である． $◼$

二つの上界の違いは，何を書き下しているかの違いである．第 $1$ の上界 $𝑛 + 2$ は $2 𝑛$ という数そのものを書き写す長さで，第 $2$ の上界 $| 𝑛 | + 𝑏$ は $𝑛$ を書いて「 $2$ の冪をとれ」と言う長さである． $| 𝑛 |$ は $𝑛$ の二進表示の桁数だから， $𝑛$ が倍になるたびに $1$ しか増えない．したがって $𝑛$ を大きくすれば，どこかで第 $2$ の上界のほうが小さくなる．どこで小さくなるかは $𝑏$ で決まり， $𝑏$ は定理 13.1.7 の証明のとおり $M$ に与えられた番号で決まるから，番号づけの取り方に依る．定理 13.1.7 が言っているのは，このように機械の側へ寄せた指示を， $U$ が定数の払いで真似できるということである．

本節は，記述を測る規約を $U$ 一つに固定した．次節はその規約のもとで，短く書ける対象がどれだけあるかを数える．数えられるのは，指示のほうがビット列で，長さで区切れば本数が決まるからである．

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