コンプリート・ナンバリング

計算可能性理論において、コンプリート・ナンバリング（）はアクセプタブル・ナンバリングの一般化であり、1963年にアナトリー・マルツェフによって導入された。クリーネの再帰定理やライスの定理などは、元々はアクセプタブル・ナンバリングを持つ計算可能関数の集合に対して証明されたものであるが、これらはコンプリート・ナンバリングを持つ任意の集合でも成立する。
定義.
集合 formula_1 のナンバリング formula_2 が（元 formula_3 に対し）コンプリートとは、任意の部分計算可能関数 formula_4 に対して全域計算可能関数 formula_5 が存在して次を満たすことをいう：
ナンバリング formula_2 がプリコンプリートとは次を満たすことをいう：