スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

--.--.-- | | スポンサー広告

オメガ数

先月の日経サイエンスに、
『ゲーデルを超えて オメガ数が示す数学の限界』というの記事がありました。

数学は有限個の原理(公理)からすべての数学的真理(定理)を演繹できるというヒルベルトの立場は、ゲーデルの不完全性定理によって覆された。つまり、ゲーデルは数学(十分強力な形式的体系)には、それ自身では証明できない定理が存在するということを示したのであった。ゲーデルは自己言及のパラドックスによりそのことを示したが、さらに数学で証明できない定理は無数に存在するということを示すのがオメガ数である。

オメガ数とは
すべてのプログラムの集合を考える。そのなかから一つプログラムを選んで、それがいずれ停止するプログラムである確率がオメガ数である。Nビット以下のプログラムならばたかだかN回の計算量で停止するか否かを判断できる。たとえば3ビットのプログラムの集合のなかで停止するのは110(二進数表記)だけだったとするとオメガ数は1/8である。いま、すべてのプログラムの集合を考えているのでオメガ数は、
omega.png
である。ただし、Nはプログラムのビット長、kNはNビット長のプログラムのうち停止するプログラムの数である。

結局、有限のメジャーで無限(に続く乱数)をはかろうとしても無理だということ(有限のメジャーを無限回使わなければならない)。

数学には公理を用いて証明できない定理が存在して、それを既約であると認め新しい公理を付け加えるしかないと著者は主張しています。

ちなみに、Douglas R. Hofstadterは『ゲーデル,エッシャー,バッハ』のなかの第18図で、定理、証明できない定理、定理の否定、証明できない定理の否定の4つの関係を表しています。この図を見るとオメガ数のような証明できない定理が無数にあることは、もう既に予期されていたことなのではないかと思えてきます。

余談ですが、意識が論理的に物理的なものに還元できないから、意識を新たな法則として付け加えるのがよいのではないかと考えているのがHofstadterの弟子?のChalmersです。

スポンサーサイト

2006.06.01 | | Comments(0) | Trackback(0) | 雑記

コメント

コメントの投稿


秘密にする

«  | HOME |  »

FC2カウンター

ブロとも申請フォーム

この人とブロともになる

ブログ内検索


上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。