Chaitinの定数

同義語:Chaitin's constant停止確率halting probability

概要

Chaitinの定数(Chaitin's constant)とは、最適な接頭的機械 $U$ に対して $\Omega_U=\sum_{U(y)\text{ が停止}}2^{-|y|}$ で定まる実数で、$U$ の入力を硬貨投げで与えたときの停止確率である。先頭 $n$ ビットから長さ $n$ 以下のプログラムの停止が判定でき、接頭複雑性は $n-c$ 以上なので、2進展開は Martin-Löf ランダムである。定理の全体が計算可能枚挙でき桁の文について健全な理論は、$\Omega_U$ の桁を有限個しか決められない。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: Kolmogorov複雑性, 停止問題, Gödelの不完全性定理

Chaitinの定数 $\Omega$ は、でたらめなプログラムを $0,1$ の硬貨投げで打ち込むとき、計算機が停止する確率である。1 個の実数だが、先頭の $n$ ビットには長さ $n$ 以下のプログラムの停止の情報がすべて詰まっている。そのため $\Omega$ の 2 進展開はどの効果的な検定も通るランダムな列になり、定理を計算可能枚挙できる算術の健全な理論は $\Omega$ の桁を有限個しか決められない。
この記事では接頭的機械から始めて、$\Omega$ のランダム性と、その桁についての不完全性定理までを証明する。

接頭的機械と $\Omega$

$\{0,1\}^*$ を有限 2 進列の全体、$|y|$ を長さとする。どの 2 つも一方が他方の真の接頭辞にならない集合を 接頭自由 という。

接頭的機械と接頭複雑性

部分計算可能関数 $M\colon\{0,1\}^*\to\{0,1\}^*$ で定義域が接頭自由なものを 接頭的機械 という。$K_M(x):=\min\{|y|: M(y)=x\}$(無ければ $\infty$)とする。接頭的機械 $U$ が 最適 であるとは、どの接頭的機械 $M$ に対しても定数 $c_M$ があり、すべての $x$ で $K_U(x)\le K_M(x)+c_M$ となることをいう。最適な $U$ を 1 つ固定して $K:=K_U$ と書き、接頭複雑性 とよぶ。

Kolmogorov複雑性 の $C$ と同じ発想で、プログラムが自分の終わりを自分で知っている点だけが違う。接頭自由な集合 $S$ については、長さ $|y|$ の $y\in S$ で始まる無限列の全体(測度 $2^{-|y|}$)は互いに素なので、Kraft の不等式 $\sum_{y\in S}2^{-|y|}\le1$ が成り立つ。

最適な接頭的機械の存在

最適な接頭的機械がある。

最適な接頭的機械の存在

部分計算可能関数の標準的な列挙を $\varphi_e$ とする。$M_e$ を次の機械とする:$\varphi_e$ の停止を全入力について並行に探し、$\varphi_e(y)$ の停止を見つけるたびに、すでに受理した列と $y$ が接頭辞の関係になければ $y$ を受理する。$M_e(y)$ は受理された $y$ についてだけ定義され、値は $\varphi_e(y)$ である。$M_e$ は接頭的機械で、$\varphi_e$ が初めから接頭的機械なら $M_e=\varphi_e$ である。
$U(0^e1y):=M_e(y)$ と定めると $U$ の定義域は接頭自由で、$M=\varphi_e$ について $K_U\le K_M+e+1$ である。$\square$

Chaitinの定数

最適な接頭的機械 $U$ に対し、
$$ \Omega_U:=\sum_{U(y)\text{ が停止}}2^{-|y|} $$
を $U$ の Chaitinの定数(停止確率)という。$U$ の入力として公平な硬貨投げの列を読ませるとき、$U$ が有限個のビットを読んで止まる確率である。$U$ を固定した議論では $\Omega$ と書く。

値は $U$ の選び方に依存する(ex-many-ones)。したがって「1 つの定数」というより、定まった性質をもつ実数の族である。段階 $s$ までに長さ $s$ 以下で止まった $y$ の和を $\Omega_s$ と書く。$\Omega_s$ は計算可能な有理数の増加列で $\Omega$ に収束する。こうした実数を 左 c.e. という。
$\Omega$ の 2 進展開の先頭 $n$ ビットの列を $\Omega{\restriction}n$、それを小数と読んだ有理数を $0.(\Omega{\restriction}n)$ と書く。有限小数の場合の 2 通りの展開は、次の命題で排除される。

計算不可能性

$\Omega$ は計算可能な実数でない。とくに無理数である。

計算不可能性

計算可能だとする。与えられた $y$ について、$\Omega-\Omega_s< 2^{-|y|}$ となる $s$ を計算で見つけられる。$y$ が段階 $s$ より後で止まれば和が $2^{-|y|}$ 以上増えるので矛盾する。よって $U$ の停止は判定でき、$K$ は計算可能である。
$n$ を各ビット 2 回繰り返して末尾に $01$ をつけた接頭自由な符号 $\bar n$ を使い、$M(\bar n):=$「$K(x)>n$ となる最初の $x$」と定める。$M$ は接頭的機械で、$K(M(\bar n))\le 2\log_2 n+O(1)$ である一方 $K(M(\bar n))>n$ なので、$n$ が大きいとき矛盾する。$\square$

先頭のビットが知っていること

先頭のビットによる停止判定

$\Omega{\restriction}n$ から、長さ $n$ 以下の各 $y$ について $U(y)$ が止まるかどうかを計算できる。

先頭のビットによる停止判定

$x=\Omega{\restriction}n$ とする。$\Omega$ は無理数なので $0.x<\Omega<0.x+2^{-n}$ であり、$\Omega_s>0.x$ となる $s\ge n$ が見つかる。長さ $n$ 以下の $y$ が段階 $s$ より後で止まるとすると、$\Omega\ge\Omega_s+2^{-n}>0.x+2^{-n}$ となって矛盾する。よって段階 $s$ までに止まらない $y$ は止まらない。$\square$

たとえば Goldbach 予想は、反例を順に探して見つけたら止まるプログラムの停止問題である。その長さが $n$ なら、Goldbach予想 の真偽は $\Omega{\restriction}n$ から決まる。ただし実際に $\Omega{\restriction}n$ を手にする方法はないので、これは情報の濃さの話であって解法ではない。

先頭のビットの複雑性

定数 $c$ があり、すべての $n$ で $K(\Omega{\restriction}n)\ge n-c$ である。

先頭のビットの複雑性

長さ $n$ の列 $x$ を受け取る計算 $A$ を次で定める:$\Omega_s>0.x$ となる $s\ge n$ を探し、段階 $s$ までに止まった長さ $n$ 以下の $y$ の出力 $U(y)$ を並べ、その一覧に無い最初の列 $z$ を出す。
$x=\Omega{\restriction}n$ のとき、lem-halting-from-bits により一覧は長さ $n$ 以下で止まるプログラムの出力の全部なので、$K(z)>n$ である。
一方 $M(w):=A(U(w))$ は定義域が $U$ の定義域に含まれるので接頭的機械であり、$K(z)\le K(x)+c_M$ である。よって $n< K(\Omega{\restriction}n)+c_M$ が成り立つ。$\square$

複雑性とランダム性を結ぶ

次の補題は、要求された長さのプログラムを実際に割り当てる道具である。

Kraft–Chaitinの補題

計算可能に列挙された要求の列 $(l_i,\sigma_i)$($l_i\in\mathbb{N}$、$\sigma_i\in\{0,1\}^*$)が $\sum_i2^{-l_i}\le1$ をみたすとする。このとき接頭的機械 $M$ と列 $y_i$ があり、$|y_i|=l_i$ かつ $M(y_i)=\sigma_i$ である。したがって $K(\sigma_i)\le l_i+c_M$ である。

Kraft–Chaitinの補題

区間 $[0,1)$ の未使用部分を、長さの相異なる 2 進区間(列 $y$ に対応する長さ $2^{-|y|}$ の区間)の有限和として保つ。最初の未使用部分は $[0,1)$ である。
要求 $l=l_i$ が来たとき、未使用部分の測度は $2^{-l}$ 以上である。もし全部の区間の長さが $2^{-l}$ より小さければ、長さが相異なるので和は $2^{-l}$ より小さくなるから、長さ $2^{-l}$ 以上の区間がある。その中で最小の長さ $2^{-k}$ の区間を取り、左端の長さ $2^{-l}$ の部分を $y_i$ に割り当てる。残りは長さ $2^{-l},2^{-l+1},\dots,2^{-k-1}$ の区間に 1 本ずつ分かれる。これらの長さをもつ区間は $k$ の最小性からそれまで無かったので、相異なる長さの条件は保たれる。
$y_i$ の区間は互いに素なので接頭自由であり、割り当ては計算可能である。$\square$

無限列 $X\in\{0,1\}^{\mathbb{N}}$ の空間を Cantor空間 とし、公平な硬貨投げの 測度 を $\mu$ とする。列の集合 $W$ に対し、$W$ の列で始まる $X$ の全体を $[W]$ と書く。

Martin-Löfランダム

Martin-Löf 検定 とは、一様に計算可能枚挙できる列の集合の族 $(W_m)_{m\ge1}$ で $\mu[W_m]\le2^{-m}$ をみたすものをいう。$X$ が ML ランダム であるとは、どの検定についても $X\notin\bigcap_m[W_m]$ であることをいう。

Levin–Schnorrの定理

$X$ が ML ランダムであるための必要十分条件は、定数 $c$ があってすべての $n$ で $K(X{\restriction}n)\ge n-c$ となることである。

Levin–Schnorrの定理

必要性を示す。$V_c:=\{\sigma: K(\sigma)< |\sigma|-c\}$ とおく。一様に計算可能枚挙でき、
$$ \mu[V_c]\le\sum_{\sigma\in V_c}2^{-|\sigma|}\le2^{-c}\sum_\sigma2^{-K(\sigma)}\le2^{-c} $$
である。最後は、異なる $\sigma$ の最短プログラムが異なるので Kraft の不等式が使えることによる。条件が成り立たなければ、どの $c$ でも $X\in[V_c]$ であり、$X$ はこの検定に落ちる。
十分性を示す。$X\in\bigcap_m[W_m]$ とする。$W_{2m}$ の列を順に細分して、$[W_{2m}]$ を変えずに接頭自由な $W'_{2m}$ に取り替える。$\sigma\in W'_{2m}$ なら $2^{-|\sigma|}\le2^{-2m}$ なので $|\sigma|\ge2m$ であり、要求 $(|\sigma|-m,\sigma)$ を出せる。重みの和は
$$ \sum_{m\ge1}\sum_{\sigma\in W'_{2m}}2^{m-|\sigma|}=\sum_{m\ge1}2^m\mu[W_{2m}]\le\sum_{m\ge1}2^{-m}=1 $$
である。lem-kraft-chaitin により、$\sigma\in W'_{2m}$ について $K(\sigma)\le|\sigma|-m+c'$ である。$X$ の接頭辞 $X{\restriction}n$ が $W'_{2m}$ に入るので $K(X{\restriction}n)\le n-m+c'$ となり、$m$ は任意だから条件は成り立たない。$\square$

SUV17 Theorem 90・Theorem 92 は同じ判定法を一様な枠組みで述べ、定義は同書 §3.3 にある。上の証明は書き直したものである。

Ωのランダム性

$\Omega$ の 2 進展開は ML ランダムである。

実際、thm-omega-complexity と thm-levin-schnorr を合わせればよい。CDS02 Theorem 2 はこれを Chaitin の結果として述べる(Cha75)。SUV17 Theorem 100 は極大の半測度の和としての形で同じことを述べる。SUV17 が述べる通り、ML ランダムな列では 0 と 1 の頻度は $1/2$ に収束する(この記事では証明しない)。
逆向きの特徴づけもある。$\alpha\in(0,1)$ について、$\alpha$ が左 c.e. かつ ML ランダムであることと、$\alpha$ がある最適な機械の $\Omega$ であることは同値である(CDS02 Theorem 3 が Slaman の結果として引く。この記事では証明しない)。

停止問題との Turing 同値

$\Omega$ と停止問題 $\emptyset'$ は Turing次数 が等しい。

停止問題との Turing 同値

$\Omega\le_T\emptyset'$:有理数 $q$ について「$\Omega_s>q$ となる $s$ がある」は $\emptyset'$ で判定できる。これを $2^{-n}$ の倍数の $q$ に使えば先頭 $n$ ビットが分かる。
$\emptyset'\le_T\Omega$:$M(0^e1)$ を $\varphi_e(e)$ が止まるときだけ止まる接頭的機械とする。$M=M_d$ の添字 $d$ について $U(0^d10^e1)$ は同じ停止の挙動をもつので、lem-halting-from-bits により $\Omega$ の先頭 $d+e+2$ ビットから判定できる。$\square$

桁についての不完全性定理

理論 $T$ と、文を与える計算可能な写像 $(i,b)\mapsto\beta(i,b)$ を考える。$\beta(i,b)$ は「$\Omega$ の第 $i$ 桁は $b$ である」を表す文とする。算術的階層 でいえば、$\Omega_s$ が計算可能なので、この文は算術の $\Delta_2$ の文として書ける。

Ωの桁についての不完全性定理

$T$ の定理の全体が計算可能枚挙でき、$T$ が $\beta(i,b)$ の形の文について健全である(定理になる $\beta(i,b)$ は正しい)とする。このとき $\beta(i,b)$ が定理になる $i$ は有限個である。

Ωの桁についての不完全性定理

無限個あるとする。定理を列挙して、相異なる $i_1,i_2,\dots$ と $T$ が証明する値 $b_1,b_2,\dots$ を計算可能に取り出せる。$W_m$ を、長さ $\max(i_1,\dots,i_m)$ の列で第 $i_j$ 桁が $b_j$($j\le m$)であるものの全体とする。$\mu[W_m]=2^{-m}$ で、$(W_m)$ は Martin-Löf 検定である。健全性から $\Omega\in\bigcap_m[W_m]$ となり、cor-omega-random に矛盾する。$\square$

Peano算術 や集合論を、算術の文について健全だと仮定すれば、$T$ として使える。CDS02 Theorem 5 は集合論 ZFC についてこの形で述べている。ここで要るのは無矛盾性でなく健全性である。無矛盾性だけで足りるかどうかは、上の証明からは分からない。Gödelの不完全性定理 が証明不可能な文の存在を述べるのに対し、この定理は 1 つの実数の桁のうち決められないものが余有限個あることを述べる。

桁がいくつ決まるかは機械による

$k\ge1$ を固定する。接頭的機械 $V$ を、$j< k$ について $V(0^j1):=\lambda$(空列)、$V(0^ky):=U(y)$ で定める。定義域は接頭自由であり、$K_V\le K_U+k$ なので $V$ も最適である。
$$ \Omega_V=\sum_{j< k}2^{-j-1}+2^{-k}\Omega_U=1-2^{-k}+2^{-k}\Omega_U $$
なので、$\Omega_V$ の先頭 $k$ ビットはすべて 1 である。prop-optimal の証明の $U$ なら、定義域の接頭自由性と、明らかに止まらない $\varphi_e$ の添字 $e$ からの $\Omega_U\le1-2^{-e-1}$ が弱い算術で証明できるので、弱い算術を含む $T$ はこの $k$ 個の桁を決められる(CDS02 §4 にも同じ趣旨の注意がある)。よって決まる桁の個数に、機械によらない上界はない。

逆の極端もある。$\alpha\in(0,1/2)$ が左 c.e. で ML ランダムなら、$\alpha$ を停止確率としてもち、ZFC が(算術的に健全なら)1 桁も決められない機械がある(CDS02 Theorem 8。Solovay の定理とされる。この記事では証明しない)。特定のレジスタ機械については先頭の 64 ビットが計算された例もある(CDS02 §7)。

反例:どの仮定が効いているか

外す仮定例起きること種類
機械の定義域が接頭自由恒等写像 $y\mapsto y$和が発散し、確率にならない定義できなくなる
機械の最適性ex-computable-halting$\Omega$ が有理数になる主張が成り立たない
定理の計算可能枚挙正しい $\beta(i,b)$ を全部公理にした理論全部の桁が決まる主張が成り立たない
理論の健全性矛盾した理論すべての $\beta(i,b)$ が定理になる主張が成り立たない
最適でない接頭的機械

$V(0^j1):=\lambda$($j\ge0$)だけで定義される機械は接頭的で、$\Omega_V=\sum_{j\ge0}2^{-j-1}=1$ である。この値は計算可能でランダムでない。$V$ の出力は空列だけなので、$K_V(x)=\infty$ となる $x$ があり、$V$ は最適でない。接頭的というだけでは thm-omega-complexity は出ない。

左 c.e. と計算可能の違い

$\Omega_s\to\Omega$ はすべて計算できるのに、$\Omega$ は計算可能でない。$\lvert\Omega-\Omega_s\rvert< 2^{-n}$ となる $s$ を $n$ から計算する方法がないからである。実際 lem-halting-from-bits の議論で、そのような $s$ が計算できれば停止が判定できてしまう。収束の速さが計算可能であることが、計算可能な実数と左 c.e. の実数の差である。

計算可能枚挙の行の理論では、ある文が定理かどうかを機械で確かめる手段がない。公理系として使える理論を計算可能枚挙に限るのは、決定可能性 の議論と同じ理由である。健全性の行では、矛盾した理論の定理の全体は計算可能枚挙でき、外れているのは健全性だけである。

関連項目

参考文献

[2]
Cristian S. Calude, Michael J. Dinneen, Chi-Kou Shu, Computing a glimpse of randomness, Experimental Mathematics, 2002, 361–370(Theorem 2, 3, 5, 8, §7)
[3]
Gregory J. Chaitin, A theory of program size formally identical to information theory, Journal of the ACM, 1975, 329–340

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する