Kolmogorov複雑性(Kolmogorov complexity)とは、ビット列 $x$ を出力する最も短い記述の長さ $C(x)$ のことで、記述を読み解く手順として計算可能な部分関数のうち最適なものを 1 つ固定して定める。最適な手順は存在し、手順の選び方による違いは定数で抑えられる(不変性定理)。$C(x)$ は $x$ の長さに定数を足した値以下で、長さ $n$ の列には $C(x)\ge n$ となる圧縮できない列が必ずあるが、$C$ は計算可能でなく、計算できる下界はすべて有界である。この性質から、定理を機械的に列挙でき「$C(x)>n$」を表す文に関して健全な理論では、十分大きな $n$ について「$C(x)>n$」を証明できないという Chaitin の不完全性定理が従う。
前提知識: 計算可能関数, 万能Turing機械, 停止問題
$0$ が $1000$ 個並んだビット列は「$0$ を $1000$ 個」と短く書けるが、硬貨を $1000$ 回投げて得たビット列は、たいていそれ自身を書き写すより短い書き方がない。Kolmogorov複雑性(Kolmogorov complexity)は、この「最も短い書き方の長さ」を、書き方を読み解く手順が計算可能であるという条件のもとで定義したものである。ビット列のもつ情報の量、あるいは規則性のなさ(ランダムさ)を、確率分布を持ち出さずに個々の列について測る。
読み解く手順の選び方は無数にあるが、どの手順と比べても定数の差しか損をしない「最適な」手順がある(不変性定理)。そのため、Kolmogorov複雑性は定数の差を除いて手順によらない。一方で、Kolmogorov複雑性は計算可能ではなく、計算できる下界で上に有界でないものすら存在しない。この記事では、定義と不変性定理、基本的な評価、計算不能性を証明し、応用として Chaitin による不完全性定理と、素数が無限にあることの証明を述べる。
以下、$\{0,1\}^*$ を有限のビット列(空列 $\lambda$ を含む)全体、$|x|$ を $x$ の長さとする。$\log$ は底 $2$ の対数である。自然数 $n$ は、ビット列を長さの順、同じ長さの中では辞書式に並べた $\lambda,0,1,00,01,\dots$ の $n$ 番目($0$ 番目から数える)と同一視する。この対応で $n$ に当たる列の長さは $\lfloor\log(n+1)\rfloor$ で、$n\ge1$ なら $\log n+1$ 以下である。
部分関数 $D\colon\{0,1\}^*\to\{0,1\}^*$ で計算可能なもの(ある算法が、入力 $y$ で止まるとき出力 $D(y)$ を出し、$D(y)$ が定義されないときは止まらない)を 記述の方式(description mode)または 復号器 という。$D(y)=x$ のとき $y$ を $x$ の $D$ に関する 記述 といい、
$$
C_D(x):=\min\{|y| : D(y)=x\}
$$
を $x$ の $D$ に関する 複雑性 という。記述がなければ $C_D(x)=+\infty$ とする。
たとえば恒等写像 $D(y)=y$ では $C_D(x)=|x|$ である。$D(n):=0^n$($0$ を $n$ 個並べた列。$n$ は上の対応で列とみなす)とすると $C_D(0^n)\le\log n+1$ だが、$1$ を含む列は記述をもたず複雑性が $+\infty$ になる。どの $x$ についても、$D(\lambda):=x$ とすれば $C_D(x)=0$ にできる。このように $C_D$ は $D$ の選び方で大きく変わるので、方式どうしを比べる。
記述の方式 $D_1$ が $D_2$ に 劣らない とは、定数 $c$ があって、すべての $x$ で $C_{D_1}(x)\le C_{D_2}(x)+c$ が成り立つことをいう。どの記述の方式にも劣らない記述の方式を 最適 という。
2 つの方式 $D_1,D_2$ に劣らない方式は簡単に作れる。$D(0y):=D_1(y)$、$D(1y):=D_2(y)$ とすれば、$C_D(x)\le\min(C_{D_1}(x),C_{D_2}(x))+1$ である。先頭の 1 ビットで方式を選ぶこの考えを、すべての方式に広げたのが次の定理である。
自然数 $e$ に対して、$e$ を 2 進で書いた列の各ビットを 2 回ずつくり返し($0\mapsto00$、$1\mapsto11$)、末尾に $01$ をつけた列を $\langle e\rangle$ と書く。$|\langle e\rangle|=2\lfloor\log e\rfloor+4$($e\ge1$)である。$\langle e\rangle$ の形の列は、先頭から 2 ビットずつ読んで初めて $01$ が現れたところで終わるので、$\langle e\rangle y=\langle e'\rangle y'$ なら $e=e'$ かつ $y=y'$ である。
最適な記述の方式が存在する。さらに、$D,D'$ がともに最適なら、定数 $c$ があってすべての $x$ で $|C_D(x)-C_{D'}(x)|\le c$ である。
部分計算可能関数 $\{0,1\}^*\to\{0,1\}^*$ に番号をつけ、$e$ 番目のものを $\varphi_e$ とする。万能Turing機械 により、$(e,y)\mapsto\varphi_e(y)$ は 1 つの算法 $U$ で計算できる($\varphi_e(y)$ が定義されないとき $U$ は止まらない)。$D$ を次の算法で定める。
入力 $z$ を先頭から 2 ビットずつ読み、$00$ と $11$ の並びのあとに初めて $01$ が来たら、そこまでを $\langle e\rangle$ として $e$ を読み取り、残りを $y$ として $U(e,y)$ を計算して出力する。$z$ がこの形に分けられなければ止まらない。
上の注意により分け方は一意なので、$D$ は well-defined な部分計算可能関数、すなわち記述の方式である。任意の記述の方式 $D'$ をとると、ある $e$ で $D'=\varphi_e$ である。$y$ が $x$ の $D'$ に関する最短の記述なら、$D(\langle e\rangle y)=\varphi_e(y)=x$ なので
$$
C_D(x)\le|\langle e\rangle|+|y|=C_{D'}(x)+|\langle e\rangle|
$$
である。$x$ が $D'$ に関する記述をもたなければ右辺は $+\infty$ で、不等式は自明である。定数 $c:=|\langle e\rangle|$ は $D'$ だけで決まり $x$ によらないので、$D$ は最適である。
後半:$D,D'$ が最適なら、$D$ は $D'$ に劣らず $D'$ は $D$ に劣らないので、$C_D\le C_{D'}+c_1$ と $C_{D'}\le C_D+c_2$ が成り立ち、$c:=\max(c_1,c_2)$ でよい。$\square$
最適な記述の方式 $D$ を 1 つ固定し、$C(x):=C_D(x)$ を $x$ の Kolmogorov複雑性(平易な Kolmogorov複雑性、plain Kolmogorov complexity)という。自然数 $n$ については、対応する列の複雑性を $C(n)$ と書く。
thm-kc-invariance の後半により、$D$ の選び方を変えても $C$ は有界な差しか変わらない。逆に、1 つの列 $x$ の値 $C(x)$ そのものには意味がない。最適な $D$ から $D'(\lambda):=x$、$D'(1y):=D(y)$($0$ で始まる列では定義しない)と作った方式 $D'$ は、$C_{D'}\le C_D+1$ を満たすので最適で、しかも $C_{D'}(x)=0$ だからである。Kolmogorov複雑性の主張は、つねに「定数の差を除いて」の形をとる。以下の定数 $c,c_A$ などは、固定した $D$ と、明記したもの(算法 $A$ など)だけで決まる。
この定義は Kolmogorov の 1965 年の論文による。似た考えはそれより数年前に Solomonoff が予測の理論の中で述べており、Chaitin も 1969 年に出版された論文で同じ定義を与えた(SUV17 Preface、p. xi、§1.1、p. 15)。
3 から、長さ $n$ の列は $2^n$ 個あるので、どの $n$ にも $C(x)\ge n$ となる長さ $n$ の列 $x$ がある。また、長さ $n$ の列のうち $C(x)< n-k$ となるものの割合は $2^{-k}$ より小さい。たとえば長さ $1000$ の列のうち $C(x)<990$ のものは $2^{-10}<0.001$ の割合に満たない。$C(x)\ge|x|$ となる列を 圧縮できない 列という。一様にランダムに選んだ列はほぼ圧縮できず、Kolmogorov複雑性による「ランダムな列」の見方はここから来る(SUV17 Introduction、p. 8)。
2 は「計算で情報は増えない」ことを表す。$A$ が全単射で $A^{-1}$ も計算可能なら、$C(A(x))$ と $C(x)$ の差は有界である。
2 つの列を並べた列 $xy$ の複雑性は、$C(x)+C(y)$ に対数の項を足した量で上から評価できる。単に $x$ と $y$ の記述をつなげるだけでは、どこで切れるかが分からないので、$x$ の記述の長さを先に書いておく。
定数 $c$ があって、すべての $x,y$ で $C(xy)\le C(x)+2\log(C(x)+1)+C(y)+c$ である(SUV17 Introduction の Theorem 4、p. 6)。
自然数 $m$ について $\langle m\rangle$ を前節のとおりとし、$D'(\langle m\rangle pq):=D(p)D(q)$($|p|=m$)と定める。$D'$ は、入力の頭から $\langle m\rangle$ を読み取り、続く $m$ ビットを $p$、残りを $q$ として $D(p)$ と $D(q)$ を計算し、つないで出力する算法で計算でき、分け方が一意なので記述の方式である。$p,q$ を $x,y$ の $D$ に関する最短の記述とすると、$\langle C(x)\rangle pq$ は $xy$ の $D'$ に関する記述で、その長さは $|\langle C(x)\rangle|+C(x)+C(y)$ である。$|\langle m\rangle|\le2\log(m+1)+4$($m=0$ では $4$、$m\ge1$ では $2\lfloor\log m\rfloor+4$)なので、$D$ の最適性から主張を得る。$\square$
「$1000$ 語以下では定義できない最小の自然数」という句は、$1000$ 語以下でその数を定義してしまう(Berry のパラドックス)。この句を「複雑性が $N$ を超える最初の列」に置き換え、「定義できる」を「計算できる」にすると、次の定理の証明になる。
$k\colon\{0,1\}^*\to\mathbb N$ を部分計算可能関数とし、$k(x)$ が定義されるすべての $x$ で $k(x)\le C(x)$ が成り立つとする。このとき $k$ の値は有界である(SUV17 Introduction の Theorem 6、pp. 9–10)。
$k$ の値が有界でないとして矛盾を導く。自然数 $N$ を入力とする次の算法 $B$ を考える。
段階 $s=1,2,3,\dots$ で、長さの順に並べた最初の $s$ 個の列について $k$ の計算を $s$ ステップずつ進める。ある段階で、計算が止まって $k(x)>N$ となる列 $x$ が初めて見つかったら、そのような $x$ のうち並びで最初のものを出力して止まる。
$k$ の値は有界でないので、$k(x)$ が定義されて $k(x)>N$ となる $x$ がある。その $x$ が並びの $i$ 番目で、$k(x)$ の計算が $t$ ステップで止まるなら、段階 $\max(i,t)$ までに見つかる。よって $B$ はすべての $N$ で止まり、$N\mapsto B(N)$ は計算可能な(全域の)関数である。
$k$ は $C$ の下界なので、$C(B(N))\ge k(B(N))>N$ である。一方、prop-kc-basic の 2 を $A:=B$ に当て、続いて 1 を使うと、$N\ge1$ で
$$
C(B(N))\le C(N)+c_B\le(\log N+1+c)+c_B
$$
である。合わせると、すべての $N\ge1$ で $N<\log N+c_B+c+1$ となるが、$N-\log N$ は $N\to\infty$ で無限大に発散するので、これは十分大きな $N$ で成り立たない。$\square$
ただし $C$ は上から近似できる。$c$ を prop-kc-basic の 1 の定数とし、$C^t(x)$ を、長さ $|x|+c$ 以下の $y$ のうち $D$ が $t$ ステップ以内に止まって $x$ を出力するものの長さの最小値(なければ $|x|+c$)とする。$C^t$ は $(x,t)$ の計算可能関数で、$t$ について単調に減少し、$C^t(x)\ge C(x)$ である。最短の記述の計算は有限のステップで止まるので、十分大きな $t$ で $C^t(x)=C(x)$ となる。しかし、いつ $C^t(x)$ が正しい値に達したかは分からない。このような関数を 上半計算可能 という(SUV17 Theorem 8、p. 19、§1.2、p. 21)。
thm-kc-lower-bound の論法は、形式的な理論で証明できることの限界も与える(Chaitin。SUV17 Introduction、p. 13)。
形式的な理論 $T$ が次の 3 条件を満たすとする。
結論が成り立たないとすると、どの $N$ にも、$n\ge N$ となる定理 $\sigma_{x,n}$ がある。$N$ を入力とし、$T$ の定理を順に出力させながら、$n\ge N$ となる組 $(x,n)$ を並行してたどり、$\sigma_{x,n}$(条件 2 により計算できる)が出力済みの定理と一致する組が初めて見つかったらその $x$ を出力する算法 $B$ は、すべての $N$ で止まる。条件 3 から $C(B(N))>N$ であり、prop-kc-basic の 2 と 1 から $C(B(N))\le\log N+c'$($N\ge1$)なので、十分大きな $N$ で矛盾する。後半は、どの $n$ にも $C(x)\ge n+1$ となる $x$ があることによる(prop-kc-basic の 3)。$\square$
「$C(x)>n$」は「固定した $D$ が長さ $n$ 以下のどの入力でも $x$ を出力しない」という算術の文で書ける。たとえば Peano算術 は条件 1・2 を満たし、自然数で正しい文だけを証明するなら条件 3 も満たす(SUV17 p. 13)。したがって、ほとんどすべての長い列は圧縮できないにもかかわらず、ある長さ $N$ を超えると、どの列についても「複雑性が $N$ より大きい」ことを $T$ の中で証明できない。Gödelの不完全性定理 と比べると、証明できない正しい文の具体的な形が分かることが特徴である。接頭的な機械の停止確率の桁についての同じ型の定理は Chaitinの定数 で述べる。
圧縮できない対象があることは、数え上げの議論を言い換える道具になる。最も簡単な例を示す(SUV17 §8.1、p. 233)。
素数が $p_1,\dots,p_m$ の $m$ 個しかないとする。$2^{L-1}\le x<2^L$ の自然数 $x$ は $x=p_1^{k_1}\cdots p_m^{k_m}$ と書け、$p_i\ge2$ なので各 $k_i\le\log x< L$ である。組 $(k_1,\dots,k_m)$ を $\langle k_1\rangle\cdots\langle k_m\rangle$ と符号化すると、$m$ と $p_1,\dots,p_m$ を組み込んだ算法で $x$ が復元できる。$|\langle k\rangle|\le2\log(k+1)+4\le2\log L+4$ なので、記述の方式の比較から
$$
C(x)\le m(2\log L+4)+c
$$
である($c$ は $m$ と $p_i$ で決まる)。一方、$2^{L-1}\le x<2^L$ の $x$ は $2^{L-1}$ 個あり、prop-kc-basic の 3 から、そのうち少なくとも 1 つは $C(x)\ge L-1$ を満たす。よってすべての $L$ で $L-1\le m(2\log L+4)+c$ となるが、左辺は $L$ の 1 次式、右辺は $\log L$ の 1 次式なので、十分大きな $L$ で成り立たない。したがって素数は無限にある(素数の無限性)。
この論法は「$x$ 以下の数で、素因数が $p_1,\dots,p_m$ だけのものは $(\log x+1)^m$ 個以下しかない」という数え上げの言い換えである。Kolmogorov複雑性は、こうした数え上げを個々の対象についての議論に書き直す言葉として、計算量の下界の証明(テープが 1 本の Turing機械で長さ $n$ の列を複写すると、最悪の場合 $n^2$ に比例するステップ数がかかる、など)に使われる(SUV17 §8.2、p. 233)。
| 外す仮定 | 反例 | 成り立たなくなること |
|---|---|---|
| 記述の方式が計算可能(thm-kc-invariance) | 任意の関数 $D$ を許す | 最適な方式が存在しない。どの $D$ についても、$C_D(x_n)\ge2n$ となる $x_n$ を選び $D'(n):=x_n$ とすると、$C_D(x_n)-C_{D'}(x_n)\ge2n-\log n-1$ は有界でない |
| 下界 $k$ が計算可能(thm-kc-lower-bound) | $k:=C$ | $C$ 自身は $C$ の下界で有界でない。結論の「有界」が成り立たない |
| $k$ が $C$ の下界(thm-kc-lower-bound) | $k(x):=\lvert x\rvert$ | 計算可能で有界でない。$C(x)<\lvert x\rvert$ となる $x$(たとえば長い $0^n$)で下界でない |
| 定理が帰納的可算(thm-kc-chaitin) | 正しい文 $\sigma_{x,n}$ をすべて公理に加えた理論 | 条件 2・3 は満たすが、どの $N$ についても $n\ge N$ の $\sigma_{x,n}$ が定理になる |
| 方式が最適(cor-kc-uncomputable の 3) | 恒等写像 $D_0(y)=y$ | 全域で定義域 $\{0,1\}^*$ は決定可能。$C_{D_0}(x)=\lvert x\rvert$ は計算可能 |
$D$ を任意の部分関数とする。$C_D(x)<2n$ となる $x$ は $2^{2n}-1$ 個以下なので、$C_D(x_n)\ge2n$ となる $x_n$ がある。$D'(n):=x_n$($n$ は列とみなす)は計算可能とは限らない関数で、$C_{D'}(x_n)\le|n|\le\log n+1$($n\ge1$)である。したがって $D$ は $D'$ に劣り、どの関数も、すべての関数に劣らない方式にはならない。計算可能な方式に限れば $D'$ は除かれ、thm-kc-invariance が成り立つ。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する