編號 (可計算性理論)

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

常見例子有一階邏輯哥德爾編號以及偏可計算函數的可接受編號英语admissible numbering

定義和例子

集合 的一個編號是由  的,滿的偏函數[2]:477。編號 在數字 的取值(若有定義)一般以 表示(而不是常見的函數表示 )。

編號的例子有:

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

編號的種類

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

若集合 可判定,則編號 可判定

如果 當且僅當 ,則編號 單值[3]:98;換言之, 是一個單射函數。偏可計算函數構成的集合上的單值編號又稱費德伯格編號英语Friedberg numbering

編號的大小比較

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

 [3]:100

 而且 ,則 等價於 ,記為 [3]:100

可計算編號

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

若某集合上任意可計算編號都可歸約到特定編號,則稱該特定編號為的。所有 的遞歸可枚舉子集以及所有偏可計算函數都有主編號[2]:487。偏遞歸函數上的主編號又稱為可接受編號英语admissible numbering

參見

參考文獻

  1. ^ Computability Theory - an overview | ScienceDirect Topics. www.sciencedirect.com. [2021-01-19]. (原始内容存档于2022-04-26). 
  2. ^ 2.0 2.1 2.2 2.3 2.4 Y.L. Ershov英语Yuri Ershov (1999), "Theory of numberings", Handbook of Computability Theory, Elsevier, pp. 473–506.
  3. ^ 3.0 3.1 3.2 3.3 V.A. Uspenskiĭ英语Vladimir Andreyevich Uspensky, A.L. Semenov (1993), Algorithms: Main Ideas and Applications, Springer, pp. 98–105