编号 (可计算性理论)

在可计算性理论中，编号是将自然数分配给一组对象，例如函数、有理数、图形或某种形式语言中的单词。 编号可用于将最初使用可计算函数定义在自然数上的可计算性和相关概念转移到这些不同类型的对象。

编号的常见示例包括一阶逻辑中的哥德尔编号、通用图灵机产生的描述编号以及部分可计算函数集的可接受编号。

集合 S {displaystyle S} 的编号是从 N {displaystyle mathbb {N} } 到 S 的满射偏函数 (Ershov 1999:477)。 数字 i 处的编号 ν 的值（如果定义）通常写为 νi 而不是通常的 ν ( i ) {displaystyle nu (i)!} 。

编号示例包括：

• 可计算偏函数的固定哥德尔编号 φ i {displaystyle varphi _{i}} 可用于定义递归可枚举集合的编号 W，方法是让 W(i) 为定义域 的 φi。 这个编号将是满射的（像所有编号一样）但不是单射的：将有不同的数字映射到 W 下的相同递归可枚举集。

如果它是总函数，则编号是总的。 如果部分编号的域是递归可枚举的，则始终存在等效的总编号（编号的等效定义如下）。

如果集合 { ( x , y ) : η ( x ) = η ( y ) } {displaystyle {(x,y):eta (x)=eta (y )}} 是可判定集。

如果 η(x) = η(y) 当且仅当 x=y 时，编号 η 是单值的； 换句话说，如果 η 是单射函数。 部分可计算函数集的单值编号称为 Friedberg 编号。

所有编号的集合都有预购。 让 ν 1 : N ⇀ S {displaystyle nu _{1}:mathbb {N} rightharpoonup S} 和 ν 2 : N ⇀ S {displaystyle nu _{2}: mathbb {N} rightharpoonup S} 是两个编号。

当被编号的集合 S 的对象具有足够的建设性时，通常会查看可以有效解码的编号 (Ershov 1999:486)。 例如，如果 S 由递归可枚举的集合组成，则如果对 (x,y) 的集合 (x,y) 其中 y ∈ η(x) 是递归可枚举的，则编号 η 是可计算的。 类似地，如果关系 R(x,y,z) = [g(x)](y) = z 是部分递归的 (Ershov 1999:487)，则偏函数的编号 g 是可计算的。

如果同一集合的每个可计算编号都可以归约到它，则可计算编号称为主体。 N {displaystyle mathbb {N} } 的所有递归可枚举子集的集合和所有部分可计算函数的集合都有原则编号（Ershov 1999：487）。 部分递归函数集的原则编号在文献中被称为可接受编号。