可计算性理论里,编号(英语:numbering、indexing等)是将一个集合的元素(如函数、有理数、图、或形式语言的字串)编上自然数号码。可计算性[1]以及相关的概念最先定义在自然数上,而利用编号,可将这些概念传递到上述的其他集合中作讨论。
常见例子有一阶逻辑的哥德尔编号以及偏可计算函数的可接受编号。
定义和例子
集合
的一个编号是由
到
的,满的偏函数[2]:477。编号
在数字
的取值(若有定义)一般以
表示(而不是常见的函数表示
)。
编号的例子有:
所有有限子集构成的集合上,可定义编号
,其中
,而且对任意有限非空集合
,
,其中
[2]:477。该编号是一个(偏的)双射。
- 在偏可计算函数集上,给定一哥德尔编号
,可以定义递归可枚举集合的编号
,其中
是
的定义域。该编号是满射(所有编号都是)但不是单射:不同的数可能经
映射到同一个递归可枚举集合上。
编号的种类
如果一个编号是全函数,则它是全的[3]:98。如果偏编号的定义域是递归可枚举的话,则必存在等价的全编号,等价性的定义将在下节给出。
若集合
可判定,则编号
可判定。
如果
当且仅当
,则编号
是单值的[3]:98;换言之,
是一个单射函数。偏可计算函数构成的集合上的单值编号又称费德伯格编号。
编号的大小比较
所有编号构成的集合上可以定义预序。令
和
是两编号,则
可归约到
,记为
,当且仅当存在一元偏可计算函数
,使得
。[3]:100
若
而且
,则
等价于
,记为
。[3]:100
可计算编号
如果被编号的对象
足够“可构”,人们常常会考虑能高效解码的编号[2]:486。例如,若集合
递归可枚举,则编号
是可计算的当且仅当满足
的二元组
构成的集合递归可枚举。类似地,偏函数的编号
是可计算的当且仅当关系
“
”是偏递归的[2]:487。
若某集合上任意可计算编号都可归约到特定编号,则称该特定编号为主的。所有
的递归可枚举子集以及所有偏可计算函数都有主编号[2]:487。偏递归函数上的主编号又称为可接受编号。
参见
参考文献