コンプリート・ナンバリング コンプリート・ナンバリングの概要

ウィキペディア

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

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

定義

集合 $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).\,$

例

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