コンプリート・ナンバリング
集合 A {\displaystyle A} のナンバリング ν {\displaystyle \nu } が(元 a ∈ A {\displaystyle a\in A} に対し)コンプリートとは、任意の部分計算可能関数 f {\displaystyle f} に対して全域計算可能関数 h {\displaystyle h} が存在して次を満たすことをいう:
ν ∘ h ( i ) = { ν ∘ f ( i ) if i ∈ d o m ( f ) , a otherwise . {\displaystyle \nu \circ h(i)=\left\{{\begin{matrix}\nu \circ f(i)&{\mbox{if}}\ i\in \mathrm {dom} (f),\\a&{\mbox{otherwise}}.\end{matrix}}\right.}
ナンバリング ν {\displaystyle \nu } がプリコンプリートとは次を満たすことをいう:
ν ∘ f ( i ) = ν ∘ h ( i ) i ∈ d o m ( f ) . {\displaystyle \nu \circ f(i)=\nu \circ h(i)\qquad i\in \mathrm {dom} (f).\,}