チャイティンのオメガΩ

「チャイティンのオメガΩ」とは何か。
それは「真の乱数」だ。
真の乱数、というのは「その数字そのものをもってしか表現することができない数」のことである。
例えば円周率3.141592...は、一見するとでたらめな数字の並びのようだが、「直径に対する円周の長さ」という簡潔な表現を持つ。
黄金比 1.618033... は、実は「正五角形の一辺と対角線との比」のことである。
ところが「チャイティンのオメガΩ」は、このような簡潔な表現を持つことができない。
他に例えようのない「真の乱数」なのである。

以下の説明の前に、予備知識として
　不完全性定理の最短理解 d:id:rikunora:20080524
　チューリングマシンは何を示したのか d:id:rikunora:20080525
を読んでおいた方がよいでしょう。

「チャイティンのオメガΩ」とは、「チューリングマシンの停止確率を表す数」のことである。
なんだ、簡潔な表現があるではないか、と指摘されると困るので、もう少し深く「簡潔な表現」の意味を考えてみよう。
チャイティンさんは次のように考えた。
ある数字の表現とは、その数字を算出するプログラムのことである。
もし数字を生み出すプログラムの長さの方が、結果の数字よりも長かったなら、そのプログラムには意味が無い。
わざわざプログラムを作るよりも、直接数字そのものを書き出した方が速いからである。
* もとの数字よりも短いプログラムが作成できれば、規則性がある。
* もとの数字よりも短いプログラムが作成できなければ、ランダムである。
そのように規則性とランダムを捉えよう、と考えたのである。

それでは、どうあがいても絶対に短いプログラムを作ることができないような「真の乱数」は存在するのだろうか。
その１つが「チャイティンのオメガΩ」、チューリングマシンの停止確率である。
なぜプログラムを作ることができないと言えるのか。
それは、そもそもチューリングマシンが停止するかどうかを判断するプログラムが作れないからだ。
（チューリングマシンは何を示したのか d:id:rikunora:20080525 を参照）
停止を見分けるプログラムが作れないのだから、その確率を決定するプログラムも作れるはずがない。

それだけではない。
このΩという数字の先頭からＮ桁を表示するプログラムは、必ずＮビットよりも長くなってしまうのだ。
　　※ この部分、記述が正確ではありません。
　　※ >チャイティンのオメガの有限な部分列であれば圧縮できる可能性はあります。
　　※ > しかしどんなアルゴリズムを使っても、出力する桁数を増やしていくと
　　※ > どこかで必ず逆転されます。
　　※ 詳しくは下のコメント参照. (9/17 追記)
なぜそうなるのか。
以下では、プログラムと数字を、全て０と１だけの２進数で考えることにする。
２進数で考えた場合、Ωという数字の先頭のＮ桁を見れば、Ｎビット以下の長さのプログラムが停止するか、無限ループに陥るかを知ることができるのだ。
例えば１ビット目が"1"であるプログラムが停止する場合、確率1/2で停止することになるので、Ωの１桁目は 0.1 となる。
２ビット目が"0"であっても"1"であっても停止しなかったなら、Ωの２桁目までは 0.10 となる。
３ビット目が"0"のときに停止するならば、Ωの３桁目までは 0.101 となる。
以下同様に、そのビットで止まることがあるならばΩに1が加わり、止まらなかったならΩに0が加わる。
なのでΩを見れば、プログラムが停止するかどうか、ほぼ見分けが付くわけだ。

この停止確率Ωを、Ｎ番目の２進数まで求めるプログラムをΩ(N)としよう。
Ｎ番目の２進数まで、というのは、次に見るようにＮ番目のプログラムまで調べた結果、という意味である。
（２進数なのだから、例えばＮ＝８＝2^3 のとき、長さ３ビットまでのプログラムについての結果が判明し、Ωを３桁目まで出力するものとしよう。）
チューリングマシンの停止判断を行うプログラムが作れないのだから、実はこのΩ(N)も存在しない、幻のプログラムである。
先の「チューリングマシンは何を示したのか d:id:rikunora:20080525」と同じ方法で、縦に全てのプログラムを、横に入力データを、中身に出力結果を、順番に並べた表を作ってみる。

(ProgNo.xData)	0	1	2	3	4	5	6	・・・
プログラムNo.0	10	x	x	4	62	x	・・・
プログラムNo.1	4	345	2	6342	832	x	・・・
プログラムNo.2	135	x	9999	1	62	8	・・・
プログラムNo.3	x	x	0	4	62	x	・・・
プログラムNo.4	666	143	77	5	x	36	・・・
・・・

今回の場合、表の縦はプログラムと言っても、実は単に数字（２進数）を 0, 1, 10, 11 ... と順番に並べていっただけだ。
チューリングマシンの停止を示したときには、縦横無限の広さを考えたのだが、今回はプログラムの長さがＮビット、データの長さもＮ桁までの有限の範囲だけを考えてみる。
この有限の範囲の「プログラム停止表」の中に、プログラム停止表自身を作成するプログラムは含まれているだろうか。
もし「プログラム停止表作成プログラム」があるならば、それはきっとΩ(N)のことだろう。
あるいはΩ(N)に類する「先頭のＮ桁を見ればプログラムが停止するかどうかわかる数字」であるはずだ。
ところが、そもそもΩ(N)というプログラムは存在しないし、「先頭のＮ桁を見ればプログラムが停止するかどうかわかる」ようなプログラムも存在しない。
このことから、ΩをＮ桁目まで出力するプログラムは、Ｎ桁までの表の中には存在しない、つまり（もし存在したとしても）Ｎビットより長いプログラムになってしまうのである。

これでΩを出力するプログラムは、必ずΩよりも長くなることが分かった。
以上がΩが「真の乱数」と呼ばれる所以だ。

* 参考文献
・日経サイエンス 2006/06 オメガが示す数学の限界

・数学の限界 {グレゴリー・チャイティン}
　　もちろんΩについての本なのだが、内容の半分はLISPについて。Mathematicaを持っていないと価値が半減。

・メタマス！

メタマス!―オメガをめぐる数学の冒険

上の「数学の限界」に多少不満だったのだが、最近この本が出ているのを知って、すぐさま購入。これでようやく満足できた。
変なタイトルだが、中身は数の神秘と哲学を語る、広がりのある本だ。

ここに感想が載っていた。
　http://d.hatena.ne.jp/leibniz/20071228/1199627297

• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • -

さて、以上のような説明を書いてはみたものの、どうも腑に落ちない点が幾つかある。
というより、単に私が理解していないことだと思うので、メモしておく。

* その１．
Ωの先頭からＮ桁がわかっても、どのプログラムが停止するのか完全には分からない。
例えばΩの先頭が 0.1... だったなら、１ビットのプログラム"0" か "1" のどちらか一方が停止することまではわかる。
しかし、どちらが止まるかまではわからない。
どのプログラムが停止するか完全に把握するには、２桁ずつの情報が必要だと思う。
　00 = 0 も 1 も停止しない。
　01 = 0 だけが停止する。
　10 = 1 だけが停止する。
　11 = 0 も 1 も停止する。
これなら完璧だが、数字の桁数が２倍になってしまう。
「確率がわかってるってことは、当然停止情報もわかっているはずでしょ。」
ということなのだろうか。

* その２．
Ωに関する本の説明では、プログラムとデータを分けるのではなく、いっしょくたに「コンピューターにビット列を入力する」という形をとっていた。
「コード＋データ＝プログラム」ととらえれば、いっしょくたにした方がシンプルだと思う。
上の説明では、前に書いたチューリングマシンの記事に合わせてプログラムとデータを分けて表にしてみた。
実際にΩという数字を求めるプログラムを考えたとき、「上位Ｎ桁までで停止せよ」という引数を付けるのは自然であるように思える。
例えば円周率を計算するプログラムだって、「上位１０００桁目までを計算せよ」と命じなければ、いつまでたっても終わらないではないか。
そう思って、上の説明ではΩ(N)という形にした。
オリジナルとの違いは、単に説明の仕方が違うだけで、本質的な差異ではないと思っている。

* その３．
Ωには「チューリングマシンの停止確率」という、言葉による簡潔な表現がある。
それどころか、明確な数式による簡潔な定義がある。
言葉にせよ、数式にせよ、それらは人間というプロセッサーが解釈するプログラムと考えることができる。
人間はこの簡潔な表現を聞いて、その気になればΩの計算を始めることができる。
だったら、やっぱり短い表現があるではないか、と思うのだが。
曰く、「１を聞いて１０を知る。」