ランダムネス

| コメント(0) | トラックバック(0)

苫米地英人の本でチャイティンを知ったら、たまたま、数学セミナーの2月号は、ランダムネスの特集号だった。なぜ「たまたま」かというと、チャイティンは、コルモゴロフとともに、ランダムネス研究のエースなのである。そこで、数学セミナーの記事を基に私なりにまとめてみる。

ランダムネスの重要な概念に、コルモゴロフ複雑度がある。これは、例えば、直感的には、ビット列を考えたとき、圧縮しにくさのことである。例えば、01010101と01101010では明らかに前者の方が圧縮しやすくて、コルモゴロフ複雑度が低い。

コルモゴロフ複雑度は、厳密には、次のように与えられる。すなわち、チューリングマシンが、プログラムPと入力文字列wを受け取り、文字列sを出力するとすると、コルモゴロフ複雑度K(s)は、(P,w)をあらわす文字列の長さの最小値として定義される。これを式で書くと、K(s) = min{|P||U(P) = s}である。U()は、万能チューリングマシンである。

実数αがランダムであるとは、α↑nを実数αの2進展開のn桁までとしたとき、ある定数cが存在して、K(α↑n) ≧ n - cとなることである。直感的に言うと、どの桁までをとっても、ほとんど圧縮できない数列になっている、ということである。

そこで、チャイティンの不完全性定理は、次のように記述される。
Tを、初等的な算術を含む無矛盾な形式体系とする。すると、理論Tに対して数nが存在して、どんな列sに対しても、K(s) > nは証明されない。

チャイティンの不完全性定理は、ある数nを決めたとき、その理論の範囲ではコルモゴロフ複雑度がnよりも大きいかどうか証明できない文字列sがとれる、ということであるが、これが、苫米地氏の言うように、なぜ神の不存在になるのか、さっぱり理解できない。

数学セミナーの記事には、チャイティンの不完全性定理の証明もあるけれども、私には理解を超えるので、ここには書き写さない。といいつつ、今までの記述を理解できていたということでもない。

さらには、チャイティンのΩというのもある。これは、文字列を任意に与えたとき、それがチューリングマシンを停止させる入力{P,w}をあらわす確率を示すものである。式であらわすと、dom Uを、チューリングマシンUを停止させる文字列の集合とすると、p∈dom Uについて、2-|p|を足していったものである。チャイティンは、Ωはランダムな実数であることを証明した。Ωは計算可能ではないが、具体的に構成される。

チャイティンのΩについては拡張もあるが、流石に限界になってきたので、この辺にしておく。

トラックバック(0)

トラックバックURL: http://commutative.world.coocan.jp/mt/mt-tb.cgi/2126

コメントする

このブログ記事について

このページは、あやたろうが2011年2月 1日 06:28に書いたブログ記事です。

ひとつ前のブログ記事は「EQ」です。

次のブログ記事は「ある検事の告発」です。

最近のコンテンツはインデックスページで見られます。過去に書かれたものはアーカイブのページで見られます。