編號 (可計算性理論)

可計算性理論裡，編號（英語：numbering、indexing等）是將一個集合的元素（如函數、有理數、圖、或形式語言的字串）編上自然數號碼。可計算性以及相關的概念最先定義在自然數上，而利用編號，可將這些概念傳遞到上述的其他集合中作討論。

常見例子有一階邏輯的哥德爾編號以及偏可計算函數的Template:Le。

定義和例子

集合$S$的一個編號是由$\mathbb{N}$到$S$的，滿的偏函數Template:Rp。編號$\nu$在數字$i$的取值（若有定義）一般以${\nu }_i$表示（而不是常見的函數表示$\nu (i)$）。

編號的例子有：

• $\mathbb{N}$所有有限子集構成的集合上，可定義編號$\gamma$，其中$\gamma (0)=\mathrm{\varnothing }$，而且對任意有限非空集合$A=\{a_0,\dots ,a_k\}$，$\gamma (n_A)=A$，其中$n_A=\sum _{i\le k}{2}^{a_i}$ Template:Rp。該編號是一個（偏的）雙射。
• 在偏可計算函數集上，給定一哥德爾編號$i\mapsto {\phi }_i$，可以定義遞歸可枚舉集合的編號$W$，其中$W(i)$是 ${\phi }_i$的定義域。該編號是滿射（所有編號都是）但不是單射：不同的數可能經$W$映射到同一個遞歸可枚舉集合上。

編號的種類

如果一個編號是全函數，則它是全的Template:Rp。如果偏編號的定義域是遞歸可枚舉的話，則必存在等價的全編號，等價性的定義將在下節給出。

若集合$\{(x,y):\eta (x)=\eta (y)\}$可判定，則編號$\eta$可判定。

如果$\eta (x)=\eta (y)$當且僅當$x=y$，則編號$\eta$是單值的Template:Rp；換言之，$\eta$是一個單射函數。偏可計算函數構成的集合上的單值編號又稱Template:Le。

編號的大小比較

所有編號構成的集合上可以定義預序。令${\nu }_1:\mathbb{N}\rightharpoonup S$和${\nu }_2:\mathbb{N}\rightharpoonup S$是兩編號，則${\nu }_1$可歸約到${\nu }_2$，記為${\nu }_1\le {\nu }_2$，當且僅當存在一元偏可計算函數$f$，使得

$\mathrm{\forall }i\in \mathrm{D}\mathrm{o}\mathrm{m}\mathrm{a}\mathrm{i}\mathrm{n}({\nu }_1):{\nu }_1(i)={\nu }_2\circ f(i)$。Template:Rp

若${\nu }_1\le {\nu }_2$而且${\nu }_1\ge {\nu }_2$，則${\nu }_1$等價於${\nu }_2$，記為${\nu }_1\equiv {\nu }_2$。Template:Rp

可計算編號

如果被編號的對象$S$足夠「可構」，人們常常會考慮能高效解碼的編號Template:Rp。例如，若集合$S$遞歸可枚舉，則編號$\eta$是可計算的當且僅當滿足$y\in \eta (x)$的二元組$(x,y)$構成的集合遞歸可枚舉。類似地，偏函數的編號$g$是可計算的當且僅當關係$R(x,y,z)=$「$[g(x)](y)=z$」是偏遞歸的Template:Rp。

若某集合上任意可計算編號都可歸約到特定編號，則稱該特定編號為主的。所有$\mathbb{N}$的遞歸可枚舉子集以及所有偏可計算函數都有主編號Template:Rp。偏遞歸函數上的主編號又稱為Template:Le。

參見

• Template:Le
• Template:Le
• 哥德爾數