可計算性理論裡，編號（英語：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} 。如果偏編號的定義域是遞歸可枚舉的話，則必存在等價的全編號，等價性的定義將在下節給出。
若集合\{ (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 \le \nu_2，當且僅當存在一元偏可計算函數f，使得
:\forall i \in \mathrm{Domain}(\nu_1) : \nu_1(i) = \nu_2 \circ f(i)。
若\nu_1 \le \nu_2而且\nu_1 \ge \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) = z」是偏遞歸的。
若某集合上任意可計算編號都可歸約到特定編號，則稱該特定編號為主的。所有\mathbb{N}的遞歸可枚舉子集以及所有偏可計算函數都有主編號。偏遞歸函數上的主編號又稱為。
參見
*
*
- 哥德爾數
參考文獻
评论 (0)