チャイティンの定数
大まかに言えば、p は計算可能関数 f のプログラムを表し、F はそのプログラムを入力としてそれを実行するエミュレータを表す。任意の定数 p について f(x) = F(p,x) を計算できるため、計算完備性とはあらゆる1変数の計算可能関数をこの形式で表せることを示している。
F の定義域は、x の少なくとも1つの値について F(p,x) の値が定義されている全てのプログラム p の集合である。言い換えれば、その定義域は空関数以外の関数を符号化した全てのプログラムの集合である。
関数 F が接頭属性を持つとは、定義域に p と p の適切な拡張である p′ が存在することはないことを意味する。言い換えれば、F の定義域は有限バイナリ文字列の集合上の接頭符号である。任意の完備計算可能関数の定義域は帰納的可算集合だが、帰納的集合ではない。その定義域は停止性問題とチューリング同値 (Turing equivalent) である。
0と1のあらゆる無限の並びの集合をカントール空間と呼ぶ。停止確率は、カントール空間上の通常の確率測度におけるカントール空間のある部分集合の測度と解釈できる。
カントール空間上の確率測度(fair-coin 測度とも呼ばれる)は、任意のバイナリ列 x について x で始まるバイナリ列の集合の測度が 2 となるよう定義される。それぞれの自然数 n について、カントール空間内のバイナリ列の集合 f が f(n) = 1 であるとき、その測度は 1/2 であり、n 番目の要素が 0 であるバイナリ列の集合の測度も 1/2 である。
F を接頭属性のある完備計算可能関数であるとする。F の定義域 P は次のような無限のバイナリ文字列の集合である。
P = { p 1 , p 2 , ... } {\displaystyle P=\{p_{1},p_{2},\ldots \}}
個々の文字列 pi は、カントール空間の部分集合 Si に対応する。集合 Si は pi で始まるカントール空間内の全てのバイナリ列を含む。P は接頭属性を持つため、これらの集合は重ならない。総和
∑ p ∈ P 2 − | p | {\displaystyle \sum _{p\in P}2^{-|p|}}
は次の集合の測度を表す。
⋃ i ∈ N S i {\displaystyle \bigcup _{i\in \mathbb {N} }S_{i}}
かくして、ΩF は、無作為に選択された 0 と 1 から成る無限列が、F の定義域にあるような(有限長の)ビット列から始まる確率を表している。ΩF が停止確率と呼ばれるのはこのことが理由である。