チャイティンのオメガΩ

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

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

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

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

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

この停止確率Ωを、N番目の2進数まで求めるプログラムをΩ(N)としよう。
N番目の2進数まで、というのは、次に見るようにN番目のプログラムまで調べた結果、という意味である。
(2進数なのだから、例えばN=8=2^3 のとき、長さ3ビットまでのプログラムについての結果が判明し、Ωを3桁目まで出力するものとしよう。)
チューリングマシンの停止判断を行うプログラムが作れないのだから、実はこのΩ(N)も存在しない、幻のプログラムである。
先の「チューリングマシンは何を示したのか 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 ・・・
   ・・・ 

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

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

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

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

・メタマス!

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

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

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

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


                                                                                                                                              • -

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

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

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

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