Kolmogorov複雑度的な乱数の無限存在定理からGödelの不完全性定理を導く
参考文献
$ a \in \Nとする．
$ \mathrm{len}(a) \leq K_\mathcal{U}(a)のとき，$ aは（$ \mathcal{U}において）Kolmogorov複雑度的な乱数である．以降は単に乱数であると呼ぶ． 直感的には，$ aは自分の長さ未満のプログラムで記述出来ないような数である．
もっと直感的に言えば，圧縮不能な数である．
$ \mathcal{U}における乱数は無数に存在する．
証明
$ 1 \leq aとする．
1. $ \mathcal{U}での長さが$ a未満のTuringマシンは高々$ 2^a個しか存在しない．
そのTuringマシンを全部集めた集合を$ \{f_0,f_1,\dots,f_{n}\}とする．$ n + 1 < 2^a．
2. $ \N \setminus \{\lbrack f_0 \rbrack,\lbrack f_1 \rbrack,\dots,\lbrack f_n \rbrack\}の最小値を$ bとする．
明らかに，$ b \leq n + 1である．SnO2WMaN.icon?
3. 1,2より$ b < 2^a．
したがって，$ \left\lceil \log_2(b)\right\rceil < a．
$ \left\lceil \log_2 2^a \right\rceilは自明に$ aである．
4. $ \{f_0,f_1,\dots,f_{n}\}の中に$ bを出力するTuringマシンは存在しない．
なぜなら$ \{f_0,f_1,\dots,f_{n}\}が出力しない自然数の最小値が$ bだから
したがって，$ a \leq K_\mathcal{U}(b)．
$ bは長さが$ a未満の全てのTuringマシンで定義不能．
5. ところで，$ \left\lceil \log_2(x)\right\rceilとは$ \mathrm{len}(b)のことであった．
6. 3,4,5より$ \mathrm{len}(b) \leq K_\mathcal{U}(b)．
7. したがって定義より，$ bは$ \mathcal{U}において乱数である．
8. $ aに依って$ bが決まるので，乱数は無数に存在することが示される．❏ 例
$ a = 4とする．高々Turingマシンは$ 2^3 = 8個しか存在しない．
$ \N \setminus \{0,1,2,3,4\} = \{5,6,7,\dots\}
したがって$ b = 5である．
$ 4 \leq K_\mathcal{U}(5)
以上より，$ \mathcal{U}においては$ 5は乱数．
proof
$ \mathcal{U}における乱数の集合$ R_\mathcal{U} \coloneqq \ \{ r \in \N \mid \mathrm{len}(r) \leq K_\mathcal{U}(r) \}とする．
$ \bar{R_\mathcal{U}} \coloneqq \N \setminus R_\mathcal{U}とする．
すると$ \bar{R_\mathcal{U}} = \{ a \in \N \mid K_\mathcal{U}(a) < a \}となる．
$ \{ a \in \N \mid K_\mathcal{U}(a) < \mathrm{len}(a) \}だが，$ \mathrm{len}(a)は適当な$ bとしてもよいことに注意．
$ K_\mathcal{U}(x) < yが$ \Sigma_1定義可能なので，$ \bar{R_\mathcal{U}}も$ \Sigma_1定義可能．
よって$ \bar{R_\mathcal{U}}は再帰的可算集合である． 他方，$ \bar{R_\mathcal{U}}は再帰的集合ではない． $ \bar{R_\mathcal{U}}から第2不完全性定理を導くことも出来る．