Kolmogorov複雑度
非形式的な説明
あるデータがあったとき，そのデータを生成する最小のプログラムの大きさ（長さ）
形式的定義
万能計算機$ u，有限長の文字列データ$ xに対し
Kolmogorov複雑度$ K_u(x)は以下の式で表される．
$ K_u(x) = \min_{p : u(p) = x} l(p)
万能計算機$ uがプログラム$ pを実行したときに生成される文字列が$ xに等しい$ pの中で，最小の$ pの長さ$ l(p)を$ K_u(x)とする．
例
文字列010101010101010101010101010101は，(15文字)
プログラムprint "010101010101010101010101010101"で生成される．
自明な例：15 + c文字のプログラムで生成可能．（cは定数）
プログラムprint "01" * 15で生成される．
もっと短く
定理1: Kolmogorov複雑度の自明な上限についての定理
主張
入力$ xに対して，入力の長さを$ |x|とすると，
$ K_u(x) \leq |x| + c
な定数$ cが存在する．
解説
上の例ではprint "010101010101010101010101010101"のprint ""部分の長さが$ cにあたる
定理2: Kolmogorov複雑度の相対性についての定理
主張
任意の万能計算機$ u_1,u_2と入力$ xに対して，
$ K_{u_2}(x) = K_{u_1}(x) + c
主張2
$ K_{u_2}(x) - K_{u_1}(x) = c
非形式的な説明
$ u_1で動かしても$ u_2で動かしてもKolmogorov複雑度は定数の違いしかありませんよ
どんな万能計算機をとってきてもKolmogorov複雑度にはさして影響を及ぼしませんよ
ということを意味している．
解説
このエミュレータのプログラムを$ \varepsilon_{1 \to 2}とする．
これはプログラムを一つ受け取って出力を返すプログラム（のテンプレート）である．
これ自体は単独で実行することは出来ない（出来ても意味はない．）
$ \varepsilon_{1 \to 2}の長さ$ l\left(\varepsilon_{1 \to 2}\right)は常に一定である．
$ u_2の上でプログラム$ pを動かした出力$ u_2(p)は，
$ u_1の上で
「エミュレータ$ \varepsilon_{1 \to 2}上の$ u_2で$ pを動かせ」というプログラム$ \varepsilon_{1 \to 2}(p)
出力$ u_1(\varepsilon_{1 \to 2}(p))としても取り出せる．
プログラム$ \varepsilon_{1 \to 2}(p)の長さ$ l\left( \varepsilon_{1 \to 2}(p) \right)は高々$ l(p) + l\left( \varepsilon_{1 \to 2} \right)である．
以下，誤解がなければ$ K_uの$ uは省略して単に$ Kと書く．
主張
$ Kは計算可能ではない．
証明