乱数に対する対角線論法

また，対角線論法で混乱してしまったので復習のためのメモ．
コルモゴロフ複雑は人伝にしか聞いたことがないので，用語などは適当．

適当な0,1の文字列を出力するプログラムを考える．
言語はCでもJavaでもよい．
ただし，Turing-completeで逐次的な出力ができないとまずそう．
（Turing completeが出力に関してどうなっているかよく分からない．純LISPって出力がないけどどうするんだろう．．．）

ただし，プログラムの長さは有限長とする．
このとき，次のようにプログラムは無限長の文字列も出力できることに注意する．

while(true) print "0";

このとき，0,1からなる文字列全体からなる集合を
書くことにし（無限長も含む），
プログラムの出力できる文字列の集合をSと書くことにする．
すると，Sは任意有限長の0,1文字列を含む．
なぜならば，"01100101"を出力したければ，

print "01100101";

とすればよいからである．

0,1文字列のうち，Sに含まれないものを乱数と呼ぶことにする．
任意の有限長文字列はSに含まれるので，乱数は無限の長さをもつ文字列だけからなる集合である．

Rが空集合ではない，すなわち乱数となるものが存在することは次のように言える．
の濃度は連続体濃度であり，
Sの濃度は加算無限であるので，
の濃度のほうが大きいことからRは空ではない．
さらに，このことから，Rの濃度は連続体濃度であり，殆ど全ての文字列は乱数であることがわかる．

また，Rが空でないことは対角線論法からも言うことができる．
プログラムの集合を順番に並べる．すなわち，

を全てのプログラムを並べた列とする．
並べることができることは，全てのプログラムをビット列としてみなし，辞書式順でもいれればいいので明らか．

このとき，プログラムpが出力する文字列をf(p)とし，
文字列sに対し，i番目の文字をと書くことにする．
ただし，sがi未満の長さのときはとする．
さらに，とする．

さて，

なる文字列dについて考える．
このdはどのとも異るので，Sには含まれない．
よって，であるということである．

ここまでが準備．ずいぶん長くなってしまった．

dを出力するプログラムについて考える．
これは，を順に計算していくプログラムをつくればよい．
ところが，dは乱数であるので，これを出力できるプログラムは存在しない．
どこの議論で間違えたのだろうか？

そんなに難しくはないが，混乱して時間をかけてしまった．