チャイティンの定数
ある実数が計算可能であるとは、n を入力として与えられたとき、その実数の先頭から n 桁を出力するアルゴリズムが存在する場合である。これは、実数の数字を列挙するプログラムの存在と等価である。
停止確率は計算可能ではない。この事実の証明は、Ω の先頭 n 桁を与えるアルゴリズムがあるとすれば、そのアルゴリズムを用いれば長さ n までのプログラムの停止問題が解けてしまうことに拠る。停止問題は決定不能であるため、矛盾が生じ、Ω が計算できないことが示される。
このアルゴリズムは次のように進行する。Ω の先頭 n 桁と k ≤ n が与えられているとして、アルゴリズムは F の定義域を数え上げていき、数え上げた要素群が表す確率が Ω の 2 以内である限り続ける。この時点を過ぎると、最早長さ k であるような如何なるプログラムも定義域に存在し得ない。何故なら、もしそのようなプログラムがあれば、それぞれが測度に 2 を追加することになってしまい、これは不可能だからである。従って、定義域内の長さ k の文字列の集合は、まさに既に列挙した文字列の集合である。