编号 (可计算性理论)

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

编号的例子有：

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

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

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

如果${\displaystyle \eta (x)=\eta (y)}$ 当且仅当${\displaystyle x=y}$ ，则编号${\displaystyle \eta }$ 是单值的^[3]:98；换言之，${\displaystyle \eta }$ 是一个单射函数。偏可计算函数构成的集合上的单值编号又称费德伯格编号（英语：Friedberg numbering）。

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

${\displaystyle \forall i\in \mathrm {Domain} (\nu _{1}):\nu _{1}(i)=\nu _{2}\circ f(i)}$ 。^[3]:100

若${\displaystyle \nu _{1}\leq \nu _{2}}$ 而且${\displaystyle \nu _{1}\geq \nu _{2}}$ ，则${\displaystyle \nu _{1}}$ 等价于${\displaystyle \nu _{2}}$ ，记为${\displaystyle \nu _{1}\equiv \nu _{2}}$ 。^[3]:100

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

若某集合上任意可计算编号都可归约到特定编号，则称该特定编号为主的。所有${\displaystyle \mathbb {N} }$ 的递归可枚举子集以及所有偏可计算函数都有主编号^[2]:487。偏递归函数上的主编号又称为可接受编号（英语：admissible numbering）。

• 完备编号（英语：Complete numbering）
• 圆柱化（英语：Cylindrification）
• 哥德尔数