编号 (可计算性理论)

可计算性理论里，编号（英语：numbering、indexing等）是将一个集合的元素（如函数、有理数、图、或形式语言的字串）编上自然数号码。可计算性以及相关的概念最先定义在自然数上，而利用编号，可将这些概念传递到上述的其他集合中作讨论。

常见例子有一阶逻辑的哥德尔编号以及偏可计算函数的可接受编号。

定义和例子

集合$S$的一个编号是由$\mathbb {N}$到$S$的，满的偏函数。编号$\nu$在数字$i$的取值（若有定义）一般以$\nu _{i}$表示（而不是常见的函数表示$\nu (i)$）。

编号的例子有：

• $\mathbb {N}$所有有限子集构成的集合上，可定义编号$\gamma$，其中$\gamma (0)=\emptyset$，而且对任意有限非空集合$A=\{a_{0},\ldots ,a_{k}\}$，$\gamma (n_{A})=A$，其中$n_{A}=\sum _{i\leq k}2^{a_{i}}$ 。该编号是一个（偏的）双射。
• 在偏可计算函数集上，给定一哥德尔编号$i\mapsto \varphi _{i}$，可以定义递归可枚举集合的编号$W$，其中$W(i)$是 $\varphi _{i}$的定义域。该编号是满射（所有编号都是）但不是单射：不同的数可能经$W$映射到同一个递归可枚举集合上。

编号的种类

如果一个编号是全函数，则它是全的。如果偏编号的定义域是递归可枚举的话，则必存在等价的全编号，等价性的定义将在下节给出。

若集合$\{(x,y):\eta (x)=\eta (y)\}$可判定，则编号$\eta$可判定。

如果$\eta (x)=\eta (y)$当且仅当$x=y$，则编号$\eta$是单值的；换言之，$\eta$是一个单射函数。偏可计算函数构成的集合上的单值编号又称费德伯格编号。

编号的大小比较

所有编号构成的集合上可以定义预序。令$\nu _{1}:\mathbb {N} \rightharpoonup S$和$\nu _{2}:\mathbb {N} \rightharpoonup S$是两编号，则$\nu _{1}$可归约到$\nu _{2}$，记为$\nu _{1}\leq \nu _{2}$，当且仅当存在一元偏可计算函数$f$，使得

$\forall i\in \mathrm {Domain} (\nu _{1}):\nu _{1}(i)=\nu _{2}\circ f(i)$。

若$\nu _{1}\leq \nu _{2}$而且$\nu _{1}\geq \nu _{2}$，则$\nu _{1}$等价于$\nu _{2}$，记为$\nu _{1}\equiv \nu _{2}$。

可计算编号

如果被编号的对象$S$足够“可构”，人们常常会考虑能高效解码的编号。例如，若集合$S$递归可枚举，则编号$\eta$是可计算的当且仅当满足$y\in \eta (x)$的二元组$(x,y)$构成的集合递归可枚举。类似地，偏函数的编号$g$是可计算的当且仅当关系$R(x,y,z)=$“$[g(x)](y)=z$”是偏递归的。

若某集合上任意可计算编号都可归约到特定编号，则称该特定编号为主的。所有$\mathbb {N}$的递归可枚举子集以及所有偏可计算函数都有主编号。偏递归函数上的主编号又称为可接受编号。

参见

• 完备编号
• 圆柱化
• 哥德尔数