Hatena::ブログ(Diary)

小人さんの妄想 このページをアンテナに追加 RSSフィード Twitter

2008-06-05

チャイティンのオメガΩ

チャイティンオメガΩ」とは何か。

それは「真の乱数」だ。

真の乱数、というのは「その数字そのものをもってしか表現することができない数」のことである。

例えば円周率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を知る。」


emkemk 2009/09/14 19:16 その1
"0"と"1"の両方が1ビットのプログラムということはありません。
仮に"0"が1ビットのプログラムだとすると、"1"は2ビット(以上)のプログラムの1ビット目です。"1"が1ビットのプログラムだとすると、"0"は2ビット(以上)のプログラムの1ビット目です。"0"と"1"のどちらも2ビット(以上)のプログラムの1ビット目で長さ1ビットのプログラムは存在しないということもありえますが、両方が1ビットのプログラムということだけはありません。それでは2ビット(以上)のプログラムを表現できなくなってしまうからです。どちらが(あるいは両方が)2ビット(以上)のプログラムになるかはプログラムの文法に依存します。
チャイティンのオメガが前提としている「プログラム」はプログラム自身から長さが判別可能な文法になっていなければならないのです。この性質をprefix-freeと言うらしいです。

その2
プログラムと別にデータがあるなら、そのデータもプログラムの長さとして数えなければなりません。さもなければデータをそのまま出力するプログラムを書いて、チャイティンのオメガそのものを出力したい桁数だけデータとして与えればいいということになってしまいます。
円周率の場合は、ある有限の長さのプログラムをずっと走らせ続けていれば任意の長さのビット列を延々と出力し続けることができます(別に停止する必要はありません)。
一方チャイティンのオメガでは、どんなプログラムを書いても、そのプログラム自身と同じかより短いある有限の桁数まで出力したところで無限ループに陥いるか停止するかして、それ以上出力できなくなってしまいます。
プログラムを書き換えて無限ループを回避するコードを追加したとしても、それで増やせる桁数は必ず追加したコードの長さ以下です。

その3
チャイティンのオメガを表す数式は、任意のプログラムの停止判定が超越的な立場で行えることを前提にしていますが、肝心の停止判定のアルゴリズムが与えられていないので(そんなアルゴリズムは存在しないので当然ですが)計算のしようがありません。逆にプログラムの停止判定を行うオラクルが与えられているなら、わざわざ自然言語と人間を持ち出して問題をあいまいにしなくてもオラクル付きチューリングマシンで計算できます。
ちなみに自然言語で表すことはできてもチューリングマシンで計算不可能なものはいくらでも存在するので(「すべての実数を並べるアルゴリズム」とか)、とくにチャイティンのオメガに特有の性質ではありません。

emkemk 2009/09/14 21:50 > 一方チャイティンのオメガでは、どんなプログラムを書いても、そのプログラム自身と同じかより短いある有限の桁数まで
> プログラムを書き換えて無限ループを回避するコードを追加したとしても、それで増やせる桁数は必ず追加したコードの長さ以下
これは間違いでした。チャイティンのオメガの有限な部分列であれば圧縮できる可能性はあります。しかしどんなアルゴリズムを使っても、出力する桁数を増やしていくとどこかで必ず逆転されます。

rikunorarikunora 2009/09/15 13:19 本質を突いた詳細な解説、どうもありがとうございます。
ここまですごいコメントが付くとは思ってもみませんでした。
"プロの犯行"とお見受けしました!
実はコメント頂いてから、すぐには内容を把握できず、一晩ほど考えてようやく理解しました。

その1
"0"と"1"の両方が1ビットのプログラムとして成立することはない。
なーるほど、これで納得しました。
”プログラム自身から長さが判別可能”となっている、これであればΩの1桁の数字で、
対応する長さのプログラムが停止するか、しないか、見分けがつきますね。
prefix-freeという性質を、もう少し調べてみようと思いました。

その2
これには私の思い違いが入っていました。
Ω(N) という字の形から、なんとなくΩという関数にNという引数を入れるのかな?
などと勝手に思い込んでいました。
ご指摘の通り、データもプログラムの長さに含めなければなりません。
”チャイティンのオメガそのものを出力したい桁数だけデータとして与えればいい”
これもなるほどです。
この説明を読んでから、「じゃ、プログラムとデータの違いって何なのだろう?」
という新たな疑問が湧いてきました。
たとえばプログラムの一部を圧縮してデータっぽく持っておいて、
走らせると自己展開しながら実行を続けるプログラム、などといったものは、
プログラムなのかな、データなのかな?
最初からチューリングマシンのような、アーキテクチャーがはっきりしているマシン上であれば、
明確に定義できると思うのですが。
何気にプログラム、データと呼んでいたものの区別がはっきり分かっていなかったな、と改めて思いました。

その3
”チャイティンのオメガを表す数式は、任意のプログラムの停止判定が超越的な立場で行えることを前提”
これもなるほどでした。
本来実在しない停止判定があるものとして、数式が書かれていたわけですね。
それなら表現できても、計算不能です。
オメガに限らず、自然言語は計算不可能なものをいくらでも表すことができる。
考えてみれば、これも当然でした。「計算不可能なもの」とかね。

おかげさまで、モヤモヤしていたものがだいぶ分かってきたような気がします。
いや、実際まだまだなのですけれど・・・
今後とも宜しくお願いします。

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証

トラックバック - http://d.hatena.ne.jp/rikunora/20080605/p1