跳转到内容

编号 (可计算性理论)

维基百科,自由的百科全书

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