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

計算可能性理論において、コンプリート・ナンバリング（英: complete numbering）はアクセプタブル・ナンバリングの一般化であり、1963年にアナトリー・マルツェフによって導入された。クリーネの再帰定理やライスの定理などは、元々はアクセプタブル・ナンバリングを持つ計算可能関数の集合に対して証明されたものであるが、これらはコンプリート・ナンバリングを持つ任意の集合でも成立する。

定義

集合 $A$ のナンバリング $\nu$ が（元 $a\in A$ に対し）コンプリートとは、任意の部分計算可能関数 $f$ に対して全域計算可能関数 $h$ が存在して次を満たすことをいう：

$\nu \circ h(i)=\left\{{\begin{matrix}\nu \circ f(i)&{\mbox{if}}\ i\in \mathrm {dom} (f),\\a&{\mbox{otherwise}}.\end{matrix}}\right.$

ナンバリング $\nu$ がプリコンプリートとは次を満たすことをいう：

$\nu \circ f(i)=\nu \circ h(i)\qquad i\in \mathrm {dom} (f).\,$

例

• 任意のシングルトンに対するナンバリングはコンプリートである
• 自然数上の恒等関数はコンプリートでない
• アクセプタブル・ナンバリングはプリコンプリートである

参考文献

• A.I. Mal'tsev, Sets with complete numberings. Algebra i Logika, 1963, vol. 2, no. 2, 4-29 (Russian)

関連項目

• ナンバリング
• フリードバーグ・ナンバリング