递归函数（八）

从定义 3.3 可直接得出 ≤� 是自反的。它显然也是传递的。（因为如果 �(�) 和 �(�) 是可计算函数，分别用作表示 �≤�� 和 �≤�� 的多一归约，则它们的组合 �(�(�)) 是表示 �≤�� 的多一归约。）因此，≡� 是等价关系，因此定义以下内容也是有意义的：

定义 3.6：deg�(�)——� 的多一（或 m 级）度——是 � 相对于 ≡� 的等价类——即 deg�(�)={�⊆�:�≡��}。如果 m 级包含可计算集，我们称其为可计算的，如果包含可计算可枚举集，我们称其为 c.e.。

� 的 m 度 deg(�) 将所有与其多一等价的集合集合在一起。因此，它可以被认为是确定 � 中成员资格的相对难度的抽象表示，而后者又可以用 m 可约性来解释。例如，由于我们之前的观察表明 deg�(HP)=deg�(�)，因此它们是“同样困难”的 c.e. 度。

传统上，使用粗体小写罗马字母 �,�,… 来表示度（尽管应该记住，这些是自然数集的集合）。接下来，我们定义 m 度的排序如下：

定义 3.7：设 � 和 � 为 m 度。然后我们定义

�≤��，以防存在一个集合 �∈� 和一个集合 �∈�，使得 �≤��。

�＜�� 万一 �≤�� 且 �≠�。

很容易看出 <� 是 m 度上的偏序，即非自反、反对称和传递的。因此，我们引入结构 ��=⟨{deg�(�):�⊆�},<�⟩ ，传统上称为 多一（或 m-）度。

自从 Post (1944) 引入多一度以来，与对图灵度（将在第 3.5.2 节中定义）的类似研究一起，研究 �� 的结构一直是可计算性理论研究的主要焦点。该结构的一些性质如下：

命题 3.6：

m 度在补函数下不封闭——即存在集合 � 使得 �≢��― 因而 �―∉deg(�)。

0=dfdeg�(∅)={∅} 和 �=dfdeg�(�)={�} 是不同的 m 度，它们都是（显然）可计算的。

除了 0 和 � 之外，只有一个可计算的 m 度 0�——即，对于任何可计算集 �≠∅,�≠�，0�=deg(�)。此外，0� 在 �� 中是最小的，因为对于除 0 和 � 之外的所有度 �，0�≤��。

如果 � 是 c.e.度且 �≤��，则 � 也是 c.e. 度。

存在一个最大 c.e. m 度，即 deg�(�)=df0�′，即对于所有 c.e. 度 �，�≤0�′。

任何一对 m 度 �,� 都有一个最小上界 �，即 �≤�� 且 �≤�� 且 � 小于 � 和 � 的任何其他上界 �≤�。由于我们已经看到 ≤� 也是一个偏序，这意味着 �� 也是一个上半格。

在 0� 和 �＜0�′ 之间存在一个 c.e. 度 �，即 0�＜�＜0�′。

Post (1944) 证明了第七部分，他证明了存在所谓的简单集，即 c.e. 的集合 �。并且使得 �― 是无限的，但不包含无限的 c.e. 子集。很容易看出，简单集是不可计算的。但另一方面，Post 还表明，简单集不能是 m 完全的。因此，如果 � 是简单的，则 �=dfdeg�(�)≠0�，但 �≢��，因此 �＜0�′。假设我们现在将本节开头引用的段落中的“不可解度”理解为对应于 c.e. m 度。因此，从命题 3.6 的第五部分可以得出，0�′ 确实是“最高”的此类度，并且从第七部分可以得出，存在一个较低但仍然“不可解”（即不可计算）的度。

尽管命题 3.6 的其他部分有直接的证明，但它们提供了一些见解，表明��本身是一个高度复杂的结构（例如，参见 Odifreddi 1999b: 1）。尽管如此，该定理的前两部分通常被用来说明多一度作为计算难度的抽象表示的尴尬特征——即 deg�(∅) 和 deg�(�) 的特殊行为以及集合及其补集可能存在于不同度的事实（很容易看出，� 和 �― 就是一个例子）。部分鉴于这些特征，图灵度 �� 是目前可计算性理论中研究最广泛的结构。但正如 Post 也提到的那样，它与 �� 有关，他最初无法证明存在中等不可解度的 c.e. 集。

3.5.2 图灵度

本节开头提到的相对可计算性概念现在以集合�⊆�中的可计算性进行标准分析。非正式地，我们说函数�(�→)�在�中可计算，只是存在一种算法，该算法在传统意义上是有效的，但其计算可能依赖于计算一个或多个值�(�)。反过来，这些值被假定为算法可以在一个步骤中获得，即使�(�)本身可能不可计算——例如，如果�=�。

这个概念最初是由图灵 (1939) 提出的，他描述了他所说的标准图灵机模型�的 oracle（或 o-）机器变体。 o-machine 在其他方面与普通的图灵机类似，但还具有只读的 oracle 磁带（和相应的只读磁头），在开始计算时，假设集合 � 的特征函数写在该磁带上。o-machine 的转换由其内部状态以及其读写磁带和 oracle 磁带上当前扫描的符号共同决定，从而形式化了机器在计算过程中可以“向 oracle 咨询” � 的特征函数一次或多次的想法。[27]

Kleene (1943) 描述了一般递归函数的类似想法，如下所示：

可以通过一系列一般递归模式的应用从给定函数 �1,…,� 中定义的函数 �，我们称之为给定函数中的一般递归；特别是，可以通过这些方法从头定义的函数，我们称之为一般递归。 （Kleene 1943：44）

这一特征的前半部分与第 1.5 节中给出的一般递归性的定义不同，它允许除了初始函数 0 和 �(�) 之外，函数 �1,…,�� 也可以进入定义函数 � 的方程组。这对应于假设 �1,…,�� 的值在计算过程中可用，而无需进一步计算。

还可以修改第 2.2.1 节中给出的部分递归函数的定义，以允许将这种相对化应用于另一类初始函数。由于相对化为有限函数集可以通过逐次相对化为单个函数来实现，并且函数的图也可以编码为一个集合，因此现在标准地实现如下：

定义 3.8：给定一个集合�⊆�，我们将 A-偏递归函数类 PartREC� 定义为包含初始函数 ��={0,�,���,��(�)} 并在函数

OpPartREC={Comp��,PrimRec�,Min�} 下封闭的最小偏函数类。

当然，自然数有无数个子集。但对于每个这样的�⊆�，我们仍然可以将 ��(�) 理解为一个新的原始函数符号，可用于以第 2.1.1 节中讨论的方式构造可数个 A-偏递归定义之一。因此，也可以列出所有一元 A 偏递归函数相对于其定义代码的列表，以获得统一的枚举

�0�(�)、�1�(�)、�2�(�)，…

其他元数也类似。因此不难看出，我们也可以由此获得相对化版本的结果，如 s-m-n 定理 (3.1) 和普遍性定理 (3.2)，如下所示：

定理 3.6：对于所有 �⊆�，都有一个 A 偏可计算函数 �，它是普遍的，因为对于所有一元 A 偏可计算函数 �(�→)，都有一个 �∈�，使得 ��(�,�)≃�(�)。

这些观察反过来又允许使用表达式 � 中的可计算性来描述 A 部分递归和全函数 �(�→)，以及集合 �，使得 ��(�) 在 � 中可计算。我们还使用表达式 � 中的可计算可枚举 (c.e.) 来描述集合 �，它是 A 部分递归函数的范围，并使用符号 ��� 来表示 ���(�) 的定义域。然后很容易看出，我们之前关于非可计算性的许多证明也适用于相对化设置——例如，��={�:���(�)↓} 就是一个在 � 中可计算可枚举但在 � 中不可计算的集合的例子。

我们现在可以如下陈述图灵可约性的定义：

定义 3.9：给定集合�,�⊆�, �被称为图灵可（或�-）简化为�，只要�在�中可计算。在这种情况下，我们写�≤��。

根据这个定义，只要�(�)与��(�)对于某个指标�给出的（总）�-可计算函数相吻合，�≤��。例如，如果我们采用图灵对相对可计算性的描述，我们可以将�视为描述可以将�作为预言机查阅的机器的程序。在这种情况下，�≤��意味着可以通过对输入�执行�描述的程序来决定�∈�，这反过来可能需要在计算过程中对预言机�执行查询。

我们也可以定义一个关于 ≤� 的完备性概念，如下所示：

定义 3.10：如果 � 是 c.e.，并且所有 c.e. 集 � 都满足 �≤��，则我们称 � 是图灵完备的。

很容易看出 �≤�� 意味着 �≤��。（因为如果 �(�) 是 � 到 � 的 m 约简，则考虑首先计算 �(�) 然后使用 � as 预言机检查 �(�)∈� 是否为 � 的程序，如果是则输出 1，否则输出 0。）因此，� 也是图灵完备的，即，当从图灵可约简性和多一可约简性的角度理解这一概念时，它体现了 c.e. 集之间的最大“不可解性”。

通过首先定义图灵等价的概念，可以精确地进行此类观察：

定义 3.11：如果 � 和 � 是图灵可归约的——即 �≤�� 和 �≤��——那么我们说 � 和 � 是图灵等价的，我们写为 �≡��。

再次很容易看出 ≡� 是一个等价关系，我们也可以定义图灵度的概念如下：

定义 3.12：deg�(�)——� 的图灵度——是 � 相对于 ≡� 的等价类——即 deg�(�)={�⊆�:�≡��}。

现在，我们可以定义图灵度的排序，如下所示：

定义 3.13：设 � 和 � 为图灵度。然后我们定义

�≤��，以防存在一个集合 �∈� 和一个集合 �∈�，使得 �≤��。

�＜��，以防 �≤�� 和 �≠�。

与 m 度一样，如果 � 包含可计算集，我们称 � 为可计算图灵度；如果 � 包含 c.e. 集，我们称 � 为可计算可枚举 (c.e.) 度。如果我们考虑结构

��=⟨{deg�(�):�⊆�},≤�⟩

— 即图灵度 — 很容易再次看出 ≤� 是偏序。一些观察结果说明了 �� 与多一度 �� 之间的关系，如下所示：

定理 3.7：

只有一个可计算的图灵度，表示为 0�=deg�(∅)（当与 m 度不存在歧义的可能性时，通常写为 0）。0� 由所有可计算集组成，是唯一的最小图灵度。

对于所有集合 �，且 �≡��―，因此 deg�(�)=deg�(�―)。

deg�(�) 是所有 c.e. 图灵度中的最大值。

对于任何集合 �,�，deg�(�)⊆deg�(�)，并且如果

deg�(�)≤�deg�(�)，

则

deg�(�)≤�deg�(�)。

由于 ∅ 和 � 都是（显而易见的）可计算集，根据第 i) 部分，我们有 deg�(∅)=deg�(�)=0�，这与 m 度不同。并且与第 ii 部分中的 m 度不同，deg�(�)=deg�(�―)。（因为如果我们可以通过使用 � 作为预言机的算法来决定 �，那么我们也可以使用 �― 作为预言机来决定它，只需交换我们以前的算法中获得的响应即可。）

�� 和 c.e. 度的结构

��=⟨{deg�(�):� is c.e.},≤�⟩

自 1950 年代以来，人们已经对它们进行了广泛的研究。可以通过首先定义集合的运算来考虑它们的一个最基本属性

�⊕�={2�:�∈�}∪{2�+1:�∈�}。

�⊕� 被称为 � 和 � 的有效连接，因为它编码了 � 中包含的“信息”，这些信息包含在 �⊕� 的偶数成员上，也包含在 � 的奇数成员上。如果 � 和 � 都是 c.e.，则 �⊕� 也是 c.e.。假设我们还在度数 �=deg�(�) 和 �=deg�(�) 上定义了运算

deg�(�)∨deg�(�)=dfdeg(�⊕�)。那么不难看出，�∨� 是 � 和 � 关于结构 �� 的最小上界。与 m 度一样，�� 和 �� 都形成上半格，即始终存在最小上界的偏序。[28]

给定 �⊆�，我们还可以考虑 ��={�:���(�)↓}，即上面考虑的集合，它对应于相对于 oracle � 的对角线停机问题。�� 被称为 � 的跳跃，我们也将其写为 �′。此符号还用于表示对图灵度的操作，即对某个代表 �∈� 设置 �′=deg�(�′)。下面汇总了关于集合和度数上的跳跃运算的几个事实：

命题 3.7：对于任何集合 �,�⊆�，其中 deg�(�)=� 且 deg�(�)=�：

如果 � 是可计算的，则 ��≡��。

�′ 在 � 中是 c.e.，但在 � 中不可计算。

如果 �≤��，则 �′≤��′，如果 �≡��，则 �′≡��′。

�＜��′

如果 �≤��，则 �′≤��′。

0′≤��′

如果 � 在 � 中是 c.e.，则 �≤��′。

命题 3.7 的第二部分记录了基本结果 � 是 c.e. 的事实。但对于任何集合 � 而言，可计算性都成立。由此可知 �＜��′，因此，对任何集合 � 进行跳跃操作迭代的结果都会产生一个序列

�(0)=�,�(1)=(�(0))′=�′,�(2)=(�(1))′=�″,⋮�(�+1)=(�(�))′,⋮

其中 �(0)＜��(1)＜��(2)＜�…。作为图灵度的基准，我们还定义了集合

∅0=∅,∅′=�,∅″=�′,⋮∅(�+1)=�(�)′,⋮

和度 0(�)=deg�(∅(�))。请注意，后者对应于线性排序序列

0＜�0′＜�0″＜�…＜�0(�)＜�…



图 2：图灵度��。[图 2 的扩展文本描述可用。]

如图 2 所示，可以使用此序列对第 3.2 节中定义的许多问题进行分类：

0=deg�(∅)={�:� 可计算}

0′=deg�(�)=deg�(HP)

0″=deg�(TOT)=deg�(FIN)

此类分类说明了集合在��内的位置可以理解为它距离可计算有多远的度量，即其不可解性或难度的程度。然而，与其他传统测量尺度不同，��的结构既不简单，也并不总是容易辨别。以下问题的答案是 Post (1944) 提出但未回答的事实，这为这一结论提供了一些证据：[29]

问题 3.1（Post 问题）：是否存在 c.e. 度 �，使得 0＜��＜�0′？

Friedberg (1957) 和 Muchnik (1956) 最终独立地对 Post 的问题给出了肯定的回答，他们证明了以下内容：

定理 3.8：存在 c.e. 集 � 和 �，使得 �≰�� 和 �≰��。因此，如果 �=deg�(�) 且 �=deg�(�)，则 �≰�� 且 �≰�� 因此 0＜��＜�0′ 且 0＜��＜�0′。

Friedberg-Muchnik 定理 (3.8) 的证明需要开发一种称为优先方法（或也称为伤害方法）的新技术，该方法已成为可计算性理论后续发展的核心工具。该方法提供了一种构造具有特定属性 �的 c.e. 集 �的方法，该属性可描述如下：

将 �的所需属性分为无限的要求列表 �0、�1、�2、…，使得如果满足所有 ��，则 �将满足 �；

%00

然后将这些需求与优先级相关联，这些优先级对应于构造过程中要保持其满足的顺序——例如，�0 可能具有最高（或“最重要的”）优先级，�1 具有第二高优先级，……;

然后分阶段�0,�1,�2,…,��,…构建�，每个阶段�都试图满足当前未满足的最高优先级需求��，方法是将数字添加到�的当前近似值��，或禁止其他数字在稍后阶段进入��;

可能发生的情况是，通过满足阶段�的某些要求�，该过程导致另一个要求��变得不满足（即阶段�损害��）；

在这种情况下，将参考优先级顺序以确定要采取什么行动。

在定理 3.8 中，该技术用于同时构造两个 c.e. 集 � 和 �，其度数介于 0 和 0′ 之间，方法是交替满足要求 �2�，即在偶数阶段满足 �≠{�:���(�)↓=1}，以确保 �≰��，以及满足要求 �2�+1，即在奇数阶段满足 �≠{�:���(�)↓=1}，以确保 �≰��。

自 20 世纪 60 年代以来，优先权方法的复杂应用已在可计算性理论中得到应用，以研究 �� 和 �� 的结构。[30] 可以通过这种方式或更基本的技术获得的一些说明性结果如下：

有连续（即 2ℵ0）多个不同的图灵度。具体而言，尽管对于给定的度�，�的集合使得�≤��是可数的，但�的集合使得�＜��是不可数的（Kleene & Post 1954）。

对于每个度�≢�0，都存在一个与�不可比的度�，即�≰��和�≰��。此外，存在一组 2ℵ0 成对不相容的度（Kleene & Post 1954）。

存在最小度�，即不存在�使得0＜��＜��的度（Sacks 1963b）。因此，一般来说，＜�不是稠密序。 （但根据下文事实 vii，不存在最小 c.e. 度。）

存在不具有最大下界的度 � 和 � 对。因此，尽管 �� 是上半格，但它不是格（Kleene & Post 1954）。�� 也是如此（Lachlan 1966）。

每个可数偏序集都可以嵌入 ��（Thomason 1971）。然而，�� 并非如此，因为有有限的非分配格不能嵌入 ��（Lachlan & Soare 1980）。

存在非 c.e. 度 �<�0′（Shoenfield 1960）。

对于任何 c.e. 度 �＜��，都有一个 c.e。度�，使得�＜��＜��（Sacks 1964）。因此，与一般的图灵度不同，c.e. 度是密集排序的。

对于任何 c.e. 度�＞�0，都有不可比的 c.e. 度�,�＜��，使得�=�∪�（Sacks 1963b）。

让 Th(��) 成为具有 ≡� 和 ≤� 的语言中结构��的一阶理论。Th(��) 不仅是不可判定的（Lachlan 1968），而且它实际上是与真正的二阶算术（Simpson 1977）多一等价的。

很容易证明连接操作 �∨� 是正确的，跳跃操作 �′=� 在具有 ≡� 和 ≤� 的语言中可在 �� 中定义（Shore & Slaman 1999）。

这些属性证明了 �� 作为数学结构的复杂性。一个相关的问题是 �� 是否在以下意义上是刚性的：

问题 3.2：是否存在 �� 的非平凡自同构——即映射 �:��→�� 保留 ≤� 并且不是身份？