>>422
つづき

もしこの逆に、他のプログラムがどんどん停止してあと一つでも停止すればチャイティンの定数を超えてしまう状況となり、その時点でまだゴールドバッハプログラムが停止していないなら、最早ゴールドバッハプログラムは停止し得ないので、ゴールドバッハ予想が正しいことが証明される。この方法を用いる上では、チャイティンの定数の先頭から N + 1 ビットまでの値さえ分かればよい。

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

上の説明は再帰的公理化可能理論の可証性述語がチャイティン定数から相対的に計算可能であるということを示しているに過ぎない。上記の方法で未解決問題の可証性を判定するために必要なビット長は長大であり、チャイティン定数の正確な値を必要なだけ求めることは困難である。仮に必要なだけのビットが求められたとしても、上のアルゴリズムの計算量は膨大である。したがって上記の方法で未解決問題の可証性を判定することが実際的な意味で可能であるというわけではない。

属性
チャイティンの定数 Ω は以下のような属性を有する。

・アルゴリズム的無作為性を有する。すなわち、任意の特定のプログラミング言語において定数 C が存在し、その言語で書かれたチャイティンの定数の先頭 n ビットを出力して停止するプログラムは、(n ? C) ビットより短くなることはない。
・正規数である。すなわち、歪みの無い硬貨を投げて決めたように各数字が等しい確率で出現する。
・計算可能数ではない。すなわち、バイナリ列として展開した値を計算できる関数は存在しない。
・停止問題とチューリング同値

停止確率の計算不可能性
ある実数が計算可能であるとは、n を入力として与えられたとき、その実数の先頭から n 桁を出力するアルゴリズムが存在する場合である。これは、実数の数字を列挙するプログラムの存在と等価である。

つづく