編號 (可計算性理論)

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

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

 定義和例子 

集合的一個編號是由到的，滿的偏函數 (1999), "Theory of numberings", Handbook of Computability Theory, Elsevier, pp. 473–506.。編號在數字的取值（若有定義）一般以表示（而不是常見的函數表示）。

編號的例子有：
 所有有限子集構成的集合上，可定義編號，其中，而且對任意有限非空集合，，其中 。該編號是一個（偏的）雙射。 
 在偏可計算函數集上，給定一哥德爾編號，可以定義遞歸可枚舉集合的編號，其中是 的定義域。該編號是滿射（所有編號都是）但不是單射：不同的數可能經映射到同一個遞歸可枚舉集合上。

 編號的種類 

如果一個編號是全函數，則它是全的, A.L. Semenov (1993), Algorithms: Main Ideas and Applications, Springer, pp. 98–105。如果偏編號的定義域是遞歸可枚舉的話，則必存在等價的全編號，等價性的定義將在下節給出。

若集合可判定，則編號可判定。

如果當且僅當，則編號是單值的；換言之，是一個單射函數。偏可計算函數構成的集合上的單值編號又稱。

 編號的大小比較 

所有編號構成的集合上可以定義預序。令和是兩編號，則可歸約到，記為，當且僅當存在一元偏可計算函數，使得
。

若而且，則等價於，記為。

 可計算編號 

如果被編號的對象足夠「可構」，人們常常會考慮能高效解碼的編號。例如，若集合遞歸可枚舉，則編號是可計算的當且僅當滿足的二元組構成的集合遞歸可枚舉。類似地，偏函數的編號是可計算的當且僅當關係「」是偏遞歸的。

若某集合上任意可計算編號都可歸約到特定編號，則稱該特定編號為主的。所有的遞歸可枚舉子集以及所有偏可計算函數都有主編號。偏遞歸函數上的主編號又稱為。

 參見 


 哥德爾數

參考文獻

Category:計算理論
Category:可計算性理論