チャイティンの定数
チャイティンの定数は、原理的には、ゴールドバッハ予想やリーマン予想といった数論の未解決問題を解くのに用いることが出来る。ゴールドバッハ予想とは、2より大きい全ての偶数は2つの素数の和で表せる、というものである。ある偶数が与えられたとき、それを2つの素数の和に分解するプログラムを考える。ゴールドバッハ予想が正しければ、このプログラムは偶数を次々に2つの素数に分解していくだろう。素数に分解できない偶数という反例が見つかった場合、プログラムは停止し、ゴールドバッハ予想は間違いだったことが示される。このプログラムの長さを N ビットとする。計算資源と時間に制限がない場合、チャイティンの定数を使ってゴールドバッハ予想を次のように証明できる。同時並行的に、長さが N + 1 ビット以下であるような全てのプログラムを実行する。Nビットであるゴールドバッハプログラムが停止すれば、予想は偽であったと証明される。
チャイティンの定数 Ω は以下のような属性を有する。
アルゴリズム的無作為性を有する。すなわち、任意の特定のプログラミング言語において定数 C が存在し、その言語で書かれたチャイティンの定数の先頭 n ビットを出力して停止するプログラムは、(n — C) ビットより短くなることはない。
正規数である。すなわち、歪みの無い硬貨を投げて決めたように各数字が等しい確率で出現する。
計算可能数ではない。すなわち、バイナリ列として展開した値を計算できる関数は存在しない。
q ≤ Ω となる有理数 q の集合は帰納的可算集合である。このような属性を持つ実数を再帰理論では 左-c.e.実数 と呼ぶ。
停止問題とチューリング同値であり、したがって算術的階層の Σ 1 0 {\displaystyle \Sigma _{1}^{0}} に属する。
停止問題とチューリング同値なあらゆる集合が停止確率というわけではない。より強い同値関係(Solovay equivalence) を用いて、左-c.e.実数の中で停止確率を特徴付けることができる。