Chaitinの不完全性定理
参考文献
直感的な証明
主張
$ \mathcal{S}を十分に強い証明体系とする．
任意の文字列$ sについて$ \mathcal{S} \nvdash L \leq K(s)となるような，十分大きな$ Lが存在する．
$ Lの値は$ \mathcal{S}に依存する
証明
1. この定理が偽だとすると仮定↓して，破綻することを示す．
任意の$ nについて，「ある文字列$ sについて$ \mathcal{S} \vdash n \leq K(s)」が成り立つ．
2. $ \mathcal{S}の定理は列挙可能で，何らかの方法で辞書順に並んでいるとする．
3. $ L \leq K(s)という形の定理を見つけるプログラム$ \tt findComplexString(n)を考える．
code:findComplexString
def findComplexString(n)
while i++
let cf := isCF(n)
if cf != null && cf.L >= n
return cf.s
$ \tt isCF(n)は$ n番目の定理が$ L \leq K(s)の形をしているか？をチェックし，そうならば$ \lang L,s \rangを，ダメだったらnullを返すとする．
このプログラムは$ nを入力すると，$ L \leq K(s)の形をしてかつ$ n \leq Lとなるような最初の定理の$ sを返すものだと考える．
今，このプログラムは任意の$ nに対して停止することが仮定より保証される．
4. 次のプログラム$ \tt mainを考える．$ n_0は定数とする．
code:main
def findComplexString(): ...
print findComplexString(n₀)
このとき，次の関係が成り立つ．
$ \mathrm{len}(\mathtt{main}) = \mathrm{len}(\mathtt{findComplexString}) + c + \mathrm{len}(n_0)
$ cはprint などの部分の長さで，例ではおよそ$ c = 8程度．
5. $ \mathrm{len}(\mathtt{main}) = \mathrm{len}(\mathtt{findComplexString}) + c + \mathrm{len}(n_0) < n_0となるような$ n_0を取ってくるとする．
6. このプログラム$ \tt mainは文字列$ sを出力する．
このとき，$ L \leq K(s)となる$ Lが存在し，$ n_0 \leq Lである．すなわち，$ n_0 \leq K(s)である．
ところが，$ sは$ \mathtt{main}で出力されて，$ \mathrm{len}(\mathtt{main}) < n_0であるので，$ K(s) < n_0である．
7. よって破綻する．仮定がおかしく，この定理は偽ではない．
Def. 自然数の長さ
$ x \in \Nとする．
$ xを2進数表記したとき，そのバイナリ文字列長を$ xの長さといい，$ \mathrm{len}(x)と表す．
次のように定義しても良い．$ \mathrm{len}(x)\coloneqq \left\lceil \log_2(x)\right\rceil．
例
12は，2進数表記では1100なので，$ \mathrm{len}(12)= 4．
6は110なので$ \mathrm{len}(6) = 3．
注意
任意の$ x \in \Nに対し，$ 1 \leq \mathrm{len}(x)である．
言い換えれば，$ \mathrm{len}(x) = 0となるような$ x \in \Nは存在しない．
0でさえ2進数表記では0であって，$ \mathrm{len}(0) = 0である．
Turingマシン$ fが$ n個の自然数$ \vec{x}を入力し，自然数$ yを出力することを $ f(\vec{x}) \Rightarrow yと表す．
$ fが入力$ \vec{x}に対し計算が終了しない場合，$ f(\vec{x}) \Rightarrow \bot（未定義動作）とする．
$ n = 0のときは$ f \Rightarrow yとする．
1. 入力された自然数$ xを「入力を持たず，1つの自然数を出力しうるTuringマシン$ f_xのエンコード」と解釈し $ \mathcal{U}のエンコーディング方法に依っては$ xをそのようなTuringマシンのエンコードと解釈できない場合がある．
そのような場合は$ \mathcal{U}(x) \Rightarrow \bot（未定義）とする
$ \mathcal{U}のエンコーディング方法で$ xをそのようなTuringマシンのエンコード$ f_xと解釈できたとして，$ f_xの計算が終了しない場合がある，
そのような場合も，$ \mathcal{U}(x) \Rightarrow \botとする．
まとめると，$ \mathcal{U} = \begin{cases} \bot & \text{($x$ is invalid $\mathcal{U}$-encoding)} \\ \bot & \text{($x$ is $\mathcal{U}$-encoding of $f_x$ and $f_x \Rightarrow \bot$)} \\ a & \text{($x$ is $\mathcal{U}$-encoding of $f_x$ and $f_x \Rightarrow a$)} \end{cases}
2. $ \mathcal{U}を固定する
$ \mathcal{U}への入力は
$ fの出力は計算可能であるとする．すなわち$ f \Rightarrow \lbrack f \rbrack \in \Nとする．（$ f \Rightarrow \botではない）
このとき$ \mathcal{U}(\ulcorner f \urcorner^\mathcal{U}) \Rightarrow \lbrack f \rbrackと表記する．
$ \ulcorner f \urcorner^\mathcal{U}は自然数で，$ fの$ \mathcal{U}でのGödel数という． $ \ulcorner f \urcorner^\mathcal{U}の長さを，$ fの$ \mathcal{U}での長さといい，$ \mathrm{len}_\mathcal{U}(f)と表す．
すなわち，$ \mathrm{len}_\mathcal{U}(f) \coloneqq \mathrm{len}(\ulcorner f \urcorner^\mathcal{U})である．
Turingマシン$ fの長さは$ \mathcal{U}のエンコーディングに依ることに注意． Remark.
以降
$ \mathcal{U}を固定する．
$ \mathcal{U}への入力は，必ず計算可能なTuringマシン$ fの$ \mathcal{U}のエンコーディングであると約束する． 自然数$ aとする．
$ \mathcal{U}(\ulcorner f \urcorner^\mathcal{U}) \Rightarrow aとなる$ fのうち，最小の長さの値を$ \mathcal{U}のKolmogorov複雑度といい，$ K_\mathcal{U}(a)と表す． すなわち，$ K_\mathcal{U}(a) \coloneqq \min_{\mathcal{U}(\ulcorner f \urcorner^\mathcal{U}) \Rightarrow a} \mathrm{len}_\mathcal{U}(f)
Lem.1
任意の自然数$ aに対し，$ K(a) \leq \mathrm{len}(a) + Cなる定数$ Cが存在する．
Example
下のような仮想的なプログラムを考える．
$ print "1020"
1020が4文字，print ""の部分が8文字で，すなわち，$ C = 8
こういった処理はTuringマシンに普遍的に存在する．
Lem.2
$ \{K_\mathcal{U}(a) \mid a \in \N \}は上に有界ではない．
$ K_\mathcal{U}(a)が大きくなるような自然数$ aをいくらでも取ってこれる
同じこととして，
任意の$ b \in \Nに対して$ b \leq K(a)となる$ a \in \Nが存在する．
証明
$ \mathcal{U}での長さが$ b未満の$ fは高々$ 2^b個の有限個しか存在しない．
$ \mathcal{U}で妥当な$ fについて，各々の出力$ \lbrack f \rbrackは決まっている．
したがって，$ b \leq K(a)となる$ a \in Nが存在する．（取ってこれる）
例
$ \mathcal{U}での長さが4未満の$ fは8個ある．
以下のようにすべて出力が定義されているとする．
$ \begin{gathered} f_\mathtt{0} \Rightarrow 1, f_\mathtt{1} \Rightarrow 3, f_\mathtt{10} \Rightarrow 4, f_\mathtt{11} \Rightarrow 0 \\ f_\mathtt{100} \Rightarrow 2, f_\mathtt{101} \Rightarrow 3 , f_\mathtt{110} \Rightarrow 4, f_\mathtt{111} \Rightarrow 1 \end{gathered}
このとき，$ K_\mathcal{U}(0) = 2, K_\mathcal{U}(1) = 1, K_\mathcal{U}(2) = 3, K_\mathcal{U}(3) = 1, K_\mathcal{U}(4) = 2
したがって，$ K_\mathcal{U}(5)は少なくとも4以上でなければならない．
なぜなら4未満のTuringマシンは全部出尽くしたから．
Remark.
$ K_\mathcal{U}(x) < y$ \iff$ \mathcal{U}での長さが$ y未満で，$ f \Rightarrow xとなる$ fが存在する．
以上より，$ K_\mathcal{U}(x) < yは$ \Sigma_1論理式で記述することができる．
この否定$ \lnot(K_\mathcal{U}(x) < y)すなわち$ y \leq K_\mathcal{U}(x)は$ \Pi_1論理式で記述することができる．
Lem.3
$ Tは無矛盾なら$ \Pi_1健全である．
$ Tを$ \sf PAの無矛盾な再帰的拡大理論とする．
「$ a \in \Nならば$ T \not\vdash b \leq K_\mathcal{U}(a)」となるような$ b \in \Nが存在する．
解説
Lem. 2よりこの$ bに対して$ b \leq K_\mathcal{U}(a)を満たす$ a \in \Nが存在する．
すなわち，
$ \mathcal{N} \models b \leq K_\mathcal{U}(a)なのに$ \not\vdash b \leq K_\mathcal{U}(a)（$ b \leq K_\mathcal{U}(a)は真なのに$ Tで証明不能）
証明
$ b \in \Nとする．
次の0入力Turingマシン$ Pを考える
$ Tの証明を生成し続けて，$ b \leq K_\mathcal{U}(a)という形の定理が最初に得られたとき，その定理の$ aを出力する．
$ Pは$ bの値によって長さが変わる．
$ Pの$ \mathcal{U}でのエンコーディングの長さが$ b未満になるように，$ bの値は調整するとする．
すなわち，$ \mathrm{len}_\mathcal{U} (P) < bである．
この$ Pが$ aを出力したと仮定する．
1.
$ \mathrm{len}_\mathcal{U} (P) < bであり，定義より$ \mathcal{N} \models K_\mathcal{U}(a) < bである．
2.
$ b \leq K_\mathcal{U}(a)は$ \Pi_1文であり，$ Pが$ aを出力するので$ T \vdash b \leq K_\mathcal{U}(a)．
Lem3より，$ Tが$ \Pi_1健全なので$ \mathcal{N} \models b \leq K_\mathcal{U}(a)．
1,2より破綻する．
したがって$ Pは$ aを出力しない．すなわち，停止しない．
$ b \leq K_\mathcal{U}(a)という形の証明が得られることは決して無い．
以上の議論より，$ a \in \Nならば$ T \not\vdash b \leq K_\mathcal{U}(a)．❏ 直感的な要約
1. 適当な0入力Turingマシン$ fが自然数$ aを出力するとき，$ aは$ fによって定義されるとする． 2. $ bを適当に選ぶ．$ T \vdash b \leq K_\mathcal{U}(a)だったとする．
3. 以下の破綻した結論が導かれる．
長さ$ b未満のTuringマシンでは定義不能な自然数$ a（$ b < K_\mathcal{U}(a)より）が
長さ$ b未満のTuringマシン$ Pで定義されている（$ Pの定義より）
$ T \vdash b < K_\mathcal{U}(a)であるなら$ Pはそのうち止まるので
続く