編號 (可計算性理論)

可計算性理論裡，編號（英語：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}$的遞歸可枚舉子集以及所有偏可計算函數都有主編號。偏遞歸函數上的主編號又稱為可接受編號。

參見

• 完備編號
• 圓柱化
• 哥德爾數