编号 (可计算性理论)

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

常见例子有一阶逻辑的哥德尔编号以及偏可计算函数的可接受编号（英语：admissible numbering）。

定义和例子

集合${\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）
• 哥德尔数