チャイティンの定数：Ω

http://ja.wikipedia.org/wiki/チャイティンの定数　より
「チャイティンの定数（英: Chaitin's constant）は、計算機科学の一分野であるアルゴリズム情報理論の概念で、無作為に選択されたプログラムが停止する確率を非形式的に表した実数である。グレゴリー・チャイティンの研究から生まれた。停止確率（英: Halting probability）とも。
停止確率は無数に存在するが、Ω という文字でそれらをあたかも1つであるかのように表すのが普通である。Ω はプログラムに使われている符号化方式に依存するため、特定の符号化に依存しないことを示すときは Chaitin's construction と呼ぶことがある。
個々の停止確率は正規数でかつ超越数であり、計算不可能（その数字を列挙していくアルゴリズムは停止しない）である。
・・・
停止確率の定義
接頭属性のある完備計算可能関数 F の定義域を PF とする。すると、定数 ΩF は次のように定義される。

画像：Ω

ここで、 は文字列 p の長さである。これは、F の定義域にあるそれぞれの p に対応する1つの被加数の級数である。定義域は接頭属性を持つ必要があるため、クラフトの不等式を考慮すると、この総和は0から1の間の実数に収束することが保証される。文脈上 F が明らかであれば ΩF を単に Ω と記することができるが、接頭属性のある完備計算可能関数が異なれば、Ω の値も異なる。

数論の未解決問題への応用
チャイティンの定数は原則的に、ゴールドバッハ予想やリーマン予想といった数論の未解決問題を解くのに役立つと考えられる[1]。ゴールドバッハ予想とは、2より大きい全ての偶数は2つの素数の和で表せる、というものである。ある偶数が与えられたとき、それを2つの素数の和に分解するプログラムを考える。ゴールドバッハ予想が正しければ、このプログラムは偶数を次々に2つの素数に分解していくだろう。素数に分解できない偶数という反証が見つかった場合、プログラムは停止し、ゴールドバッハ予想は間違いだったことが示される。このプログラムの長さを N ビットとする。計算資源と時間に制限がない場合、チャイティンの定数を使ってゴールドバッハ予想を次のように証明できる。同時並行的に N+1ビット以下の全てのプログラムを実行する。Nビットのゴールドバッハプログラムが停止すれば、予想は偽であったと証明される。ゴールドバッハプログラムが停止していない状態で、チャイティンの定数で示される割合を1つでも超える個数のプログラムが停止したら、ゴールドバッハプログラムは停止しないと証明され、ゴールドバッハ予想が正しいことが証明される。この手続きを行うには、チャイティンの定数の N+1 ビットまでの数値が分かればよい。

同様に、リーマン予想などの数学上の未解決問題の多くも、チャイティンの定数を使って証明（または反証）できる。」

http://ja.wikipedia.org/wiki/グレゴリー・チャイティン　より
「グレゴリー・チャイティン（Gregory "Greg" J. Chaitin, 1947年 - ）は、アルゼンチン出身、アメリカ在住の数学者、コンピュータ科学者。
60年代に情報理論の分野に、ゲーデルの不完全性定理とよく似た現象を見いだす。つまり、その分野上での決定不可能な命題を発見し別種の不完全性定理を得た。チャイティンの定理によると、十分な算術を表現可能な如何なる理論においても、如何なる数であろうともcよりも大きなコルモゴロフ複雑性を有することがその理論上では証明できないような、上限 c が存在する。ゲーデルの定理が嘘つきのパラドックスと関係しているのに対し、チャイティンの結果はベリーのパラドックスに関係している。」

http://ja.wikipedia.org/wiki/ベリーのパラドックスより
「19文字以内で記述できない最小の自然数を求める。するとその数は、「19文字以内で記述できない最小の自然数」という19文字で表現が可能であり、19文字以内で記述できない最小の自然数という定義に合致しない。
なお、誤ってリシャールのパラドックスとして紹介されることがある。」

http://ja.wikipedia.org/wiki/リシャールのパラドックス　より
「0から1までの実数をひとつ明確に定義する日本語の文をリシャール文と呼ぶことにし、このようなリシャール文を全て並べることを考える。 あらゆる正の自然数 n に対して、字数 n のリシャール文は有限個(しばしば 0 個)存在する。 よって、リシャール文をその字数の順に、字数が同じもの同士は辞書順に並べることにすれば、あらゆるリシャール文を一列に並べて、自然数で番号付けができる。

さて、次の文によってある実数を定義する:

整数部分を 0 とし、小数第 n 位の数を、第 n 番目のリシャール文によって定義される実数の小数第 n 位の数が 0 であれば 1、そうでなければ 0 、として定義される実数
この文は 0 から 1 までの実数をひとつ明確に定義しているのでリシャール文のひとつである。 このリシャール文の番号を Q とすると、この文によって定義される実数の小数第 Q 位の数は第 Q 番目のリシャール文によって定義される実数の小数第 Q 位の数、つまり自分自身と異なっていなければならない。 これは矛盾である。
なお 誤ってベリーのパラドックスがリシャールのパラドックスとして紹介されることがある。

パラドックスの回避
現在で集合論の公理系として最も広く用いられているZFCでは、「実数を明確に定義する日本語の文」といった概念は数式（論理式）によって表現できない、という理由で回避（取り扱わない）している。・・・」

よくわからないけど、、、カントールの対角線論法そのものですよね ^^;v

画像：メタマス!―オメガをめぐる数学の冒険 (単行本)
グレゴリー チャイティン (著), Gregory Chaitin (原著), 黒川 利明 (翻訳)
http://www.amazon.co.jp/メタマス-?オメガをめぐる数学の冒険-グレゴリー-チャイティン/dp/4826901380　より
「情熱の数学者グレゴリー・チャイティンが贈る、デジタル時代の数学をめぐる冒険の書。本書で扱う「オメガ数」とは、ゲーデルの不完全性定理、チューリングの停止問題の系譜にあり、そこからは、創造性とは何か、世界は離散的か連続的か、などといった根源的な問題が生じます。ライプニッツの「哲学なしには数学は極められない」という言葉に従い、数学と哲学に関する刺激的な知見を詰め込んだ本書は、新しい時代の数学を求める人に、ぜひ読んでいただきたい１冊です。 」