チャイティンの定数
停止確率の定義は「接頭属性のある完備計算可能関数」の存在に依存している。そのような関数は直観的には、どの妥当なプログラムも他の妥当なプログラムの適当な拡張として得られないという属性を持つプログラミング言語で表される。
2つの引数をとる関数 F があり、それら引数は有限なバイナリ列であり、出力として1つのバイナリ列を返すとする。この関数を計算できるチューリングマシンがあるとき、F は計算可能関数と呼ばれる。
次のような属性を持つとき、この関数 F は計算完備であると言われる。すなわち、1つの変数 x の全ての計算可能関数 f について、あらゆる x について F(p,x) = f(x) となるような定数 p が存在する場合である。これは、F が1変数のあらゆる計算可能関数をシミュレートするのに使えることを意味する。