编号 (可计算性理论)

可计算性理论里,编号(英语: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