編號 (可計算性理論)

可計算性理論裡，編號（英語：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）
• 哥德爾數

參考文獻

1. . www.sciencedirect.com. [2021-01-19]. （原始内容存档于2022-04-26）. 
2. Y.L. Ershov（英语：Yuri Ershov） (1999), "Theory of numberings", Handbook of Computability Theory, Elsevier, pp. 473–506.
3. V.A. Uspenskiĭ（英语：Vladimir Andreyevich Uspensky）, A.L. Semenov (1993), Algorithms: Main Ideas and Applications, Springer, pp. 98–105