查看“︁編號 (可計算性理論)”︁的源代码

[[可計算性理論]]裡，'''編號'''（英語：numbering、indexing等）是將一個[[集合 (數學)|集合]]的元素（如[[函數]]、[[有理數]]、[[圖 (數學)|圖]]、或[[形式語言]]的字串）編上[[自然數]]號碼。[[可計算函數|可計算性]]<ref>{{Cite web|title=Computability Theory - an overview {{!}} ScienceDirect Topics|url=https://www.sciencedirect.com/topics/mathematics/computability-theory|access-date=2021-01-19|website=www.sciencedirect.com|archive-date=2022-04-26|archive-url=https://web.archive.org/web/20220426024909/https://www.sciencedirect.com/topics/mathematics/computability-theory}}</ref>以及相關的概念最先定義在自然數上，而利用編號，可將這些概念傳遞到上述的其他集合中作討論。

常見例子有[[一階邏輯]]的[[哥德爾數|哥德爾編號]]以及偏可計算函數的{{le|可接受編號|admissible numbering}}。

== 定義和例子 ==

集合<math>S</math>的一個'''編號'''是由<math>\mathbb{N}</math>到<math>S</math>的，[[滿射|滿]]的偏函數<ref name = "Ershov">{{le|Y.L. Ershov|Yuri Ershov}} (1999), "Theory of numberings", ''Handbook of Computability Theory'', Elsevier, pp.&nbsp;473&ndash;506.</ref>{{rp|477}}。編號<math>\nu</math>在數字<math>i</math>的取值（若有定義）一般以<math>\nu_i</math>表示（而不是常見的函數表示<math>\nu(i) </math>）。

編號的例子有：
* <math>\mathbb{N}</math>所有有限子集構成的集合上，可定義編號<math>\gamma</math>，其中<math>\gamma(0) = \emptyset</math>，而且對任意有限非空集合<math>A = \{a_0, \ldots, a_k\}</math>，<math>\gamma(n_A) = A</math>，其中<math>n_A = \sum_{i \leq k} 2^{a_i}</math> <ref name="Ershov"/>{{rp|477}}。該編號是一個（偏的）雙射。 
* 在偏可計算函數集上，給定一哥德爾編號<math>i \mapsto \varphi_i</math>，可以定義[[遞歸可枚舉集合]]的編號<math>W</math>，其中<math>W(i)</math>是 <math>\varphi_i</math>的定義域。該編號是滿射（所有編號都是）但不是單射：不同的數可能經<math>W</math>映射到同一個遞歸可枚舉集合上。

== 編號的種類 ==

如果一個編號是全函數，則它是'''全'''的<ref name = "US93">{{le|V.A. Uspenskiĭ|Vladimir Andreyevich Uspensky}}, A.L. Semenov (1993), ''Algorithms: Main Ideas and Applications'', Springer, pp. 98–105</ref>{{rp|98}}。如果偏編號的[[定義域]]是[[遞歸可枚舉]]的話，則必存在等價的全編號，等價性的定義將在下節給出。

若集合<math>\{ (x,y) : \eta(x) = \eta(y)\}</math>[[递归集合|可判定]]，則編號<math>\eta</math>'''可判定'''。

如果<math>\eta(x) = \eta(y)</math>當且僅當<math>x=y</math>，則編號<math>\eta</math>是'''單值'''的<ref name = "US93"/>{{rp|98}}；換言之，<math>\eta</math>是一個單射函數。偏可計算函數構成的集合上的單值編號又稱{{le|費德伯格編號|Friedberg numbering}}。

== 編號的大小比較 ==

所有編號構成的集合上可以定義[[預序]]。令<math>\nu_1: \mathbb{N} \rightharpoonup S</math>和<math>\nu_2: \mathbb{N} \rightharpoonup S</math>是兩編號，則<math>\nu_1</math>'''可歸約到'''<math>\nu_2</math>，記為<math>\nu_1 \le \nu_2</math>，當且僅當存在一元[[可計算函數|偏可計算函數]]<math>f</math>，使得
:<math>\forall i \in \mathrm{Domain}(\nu_1) : \nu_1(i) = \nu_2 \circ f(i)</math>。<ref name = "US93"/>{{rp|100}}

若<math>\nu_1 \le \nu_2</math>而且<math>\nu_1 \ge \nu_2</math>，則<math>\nu_1</math>'''等價於'''<math>\nu_2</math>，記為<math>\nu_1 \equiv \nu_2</math>。<ref name = "US93"/>{{rp|100}}

== 可計算編號 ==

如果被編號的對象<math>S</math>足夠「可構」，人們常常會考慮能高效解碼的編號<ref name="Ershov"/>{{rp|486}}。例如，若集合<math>S</math>遞歸可枚舉，則編號<math>\eta</math>是'''可計算的'''當且僅當滿足<math>y \in \eta(x)</math>的二元組<math>(x,y)</math>構成的集合遞歸可枚舉。類似地，偏函數的編號<math>g</math>是可計算的當且僅當關係<math>R(x,y,z) = </math>「<math>[g(x)](y) = z</math>」是偏遞歸的<ref name="Ershov"/>{{rp|487}}。

若某集合上任意可計算編號都可歸約到特定編號，則稱該特定編號為'''主'''的。所有<math>\mathbb{N}</math>的遞歸可枚舉子集以及所有偏可計算函數都有主編號<ref name="Ershov"/>{{rp|487}}。偏遞歸函數上的主編號又稱為{{le|可接受編號|admissible numbering}}。

== 參見 ==
* {{le|完備編號|Complete numbering}}
* {{le|圓柱化|Cylindrification}}
* [[哥德爾編號|哥德爾數]]

==參考文獻==
{{reflist}}


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