11data_complexity.tex

\chapter{データの複雑さ(Data Complexity)}
データの複雑さを表す尺度として，\mystrong{コルモゴロフ複雑性(Kolmogorov
complexity)}がある．これは，記号長を生成するのに必要なプログラムの最小長
である．

例えば，'101010101...10 (1万桁)'は，大きなデータであるが，単純なループで
書けてしまうので，データの複雑さは小さいと言える．

\section{定式化}
プログラム$p$をある計算機$m$上で動作させた出力を$m(p)$とすると，ある記号
列$s$に対して$m(p) = s$となる最短のプログラム$p$の長さは，
\[
 K_m (s) = \min _{p | m(p) = s} \left(length(p)\right)
\]
と表せる．これがコルモゴロフ複雑性である．

\section{性質}
\begin{itemize}
 \item $s$に規則性があれば，$s$を定数として含むプログラムより短いプログ
       ラムで生成可能．
 \item 2つの異なる言語でも，一方で他方のエミュレータを作れるなら，複雑性
       はエミュレータのプログラム長(定数)しか異ならない．
\end{itemize}

この性質は，データ圧縮の可能性に関係している．つまり，コルモゴロフ複雑性
が低いデータは高い圧縮率で圧縮できる．

ただし，
\begin{mytheorem}
 \item コルモゴロフ複雑性は計算不能．
\end{mytheorem}
である(計算不能とは，どのような入力に対しても出力を出すようなアルゴリズ
ムは存在しないということであった)．

\begin{myproof}{コルモゴロフ複雑性は計算不能であることの証明}
 どのようなデータ$s$に対しても$K(s)$を導くようなアルゴリズムの存在を仮定
 して，矛盾を導く．

$K(s)$が計算できるのだから，プログラム長$l$のプログラムでは生成できない
 様な最短の記号列を求めることができる．それは，記号列を短い方から系統的
 に生成して，$K(s)$が$l$を超える最初の記号列を返すことにより実現できるは
 ずである．

このようなプログラムを$C(l)$とし，その長さを$L_C$とするとする．この関数
 を引数$l_0$で呼出した結果を返すプログラムを考える．この関数を引数$l_0$
 で呼出した結果を返すようなプログラムを考えると，その長さは
\[
 L_c + \log_2 (l_0) + \alpha
\]
となる．この長さのうち，$\log_2 (l_0)$以外は定数である．従って，$l_0$を
 大きくしていくことにより，いつかは
\[
 l_0 > L_C + \log_2 (l_0) + \alpha
\]
となるはずである．このプログラムは$C(l_0)$，即ち$l_0$の長さのプログラム
 では生成できない記号列を返すはず．それなのに長さが$l_0$未満であるため，
 矛盾である．
\end{myproof}