跳至內容

編號 (可計算性理論)

維基百科,自由的百科全書

可計算性理論裡,編號(英語: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