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

ウィキペディア

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

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/05/21 04:35 UTC 版)

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