递归函数（五）

定理 2.1 （Robinson 1947）：IT 类等于原始递归函数的 PR 类。

这说明，如果我们稍微扩大初始函数类，仍然可以通过函数迭代方案获得整个 PR 类，该方案最初看起来不如原始递归通用。有关可以在此方向上获得的进一步改进的说明，请参阅 Odifreddi (1989: ch. I.5)。

其他结果表明，如果将原始递归替换为最初看起来更通用的其他方案，PR 类也保持稳定。其中最为人熟知的是值递归过程方案，传统上用第 1 节开头简要讨论过的所谓斐波那契函数 fib(�) 来说明。该函数可定义如下：

(27)���(0)=0���(1)=1���(�+1)=���(�)+���(�−1)

此定义可轻松用于以递归方式计算 fib(�) 的值 - 例如，

fib(4)=fib(3)+fib(2)=(fib(2)+fib(1))+(fib(1)+fib(0))=((fib(1)+fib(0))+1)+(1+1)=((1+1)+1)+(1+1)=5

这产生了我们熟悉的序列 0、1、1、2， 5, 8, 13, 21, 34, 55, 89, 144,… 其中 �0=0, �1=1, 且 ��+2=��+1+��。但请注意，定义 (27) 不能直接类似于原始递归方案 (18)，因为第三子句根据 fib(�) 和 fib(�-1) 定义了 fib(�+1) 的值。但仍然可以证明 fib∈PR。一种方法是再次利用二进制编码和投影函数，首先定义一个辅助函数 �(0)=⟨0,1⟩ and

�(�+1)=⟨(�(�))1,(�(�))0+(�(�))1⟩

它枚举对 ⟨�0,�1⟩, ⟨�1,�2⟩,… 然后很容易看出 fib(�)=(�(�))0。

因此，(27) 是函数 ℎ 在 � 处的值取决于其图中的先前值 ℎ(�−1) 和 ℎ(�−2)（对于 �≥2）的一个例子。当然，也可以考虑 ℎ(�) 取决于其先前值 ℎ(0),…,ℎ(�−1) 的任意数量的情况。为此，假设我们给定 ℎ(�→,�)，然后定义

ℎ~(�→,�)=Π�=0���ℎ(�→,�)+1=⟨ℎ(�→,0),…,ℎ(�→,�)⟩。

然后我们说，如果

ℎ(�→,�) =�(�→)ℎ(�→,�+1)=�(�→,�,ℎ~(�→,�))，则ℎ(�→,�) 由从�(�→) 和 �(�→,�,�) 的值递归过程定义

ℎ(�→,0) =�(�→)ℎ(�→,�+1) =�(�→,�,ℎ~(�→,�))

假设我们现在让 CV�[�,�] 表示相应的函数运算，并让 CV 成为包含 ��PR 并在 Comp�� 和 CV� 下封闭的最小函数类。那么，由于很容易看出，如果 ℎ(�→,�) 是原始递归的，则 ℎ~(�→,�) 是原始递归的，因此我们还有以下内容：

定理 2.2（Péter 1935）：类 CV 等于原始递归函数类 PR 。

由于值过程递归在数学实践中使用，因此重要的是它不超出原始递归函数类。然而，还有许多其他可能的方法可以推广方案 (18)，包括所谓的双重递归和嵌套递归。第 1.4 节中函数 �(�,�) 的定义展示了前者，因为它在 �,� 处的值取决于它在 �−1 和 �−1 处的值，也展示了后者，因为定义的函数 �(�,�) 的出现在第三子句的右侧“嵌套”在其自身内（而不是辅助函数）。有关这些方案的原始递归函数的闭包属性的更多详细信息，请参阅 Ackermann-Péter 函数的补充。

2.2 部分递归函数 (PartREC) 和递归函数 (REC)

我们现在已经看到了两种证明存在非原始递归的数论函数的方法——即通过观察虽然只有可数个原始递归函数，但类型为 ��→� (�＞0) 的函数却有不可数个，也可以通过构造一个函数，例如 �(�,�)=��(�,�)，其增长速度比任何原始递归函数都快。第三个证明——最初由 Hilbert & Bernays (1934: ch. 7) 提出——基于这样的观察，即可以将 PR 类枚举为 �0(�)、�1(�)、�2(�)，…——例如，通过哥德尔对第 2.1.1 节末尾考虑的定义类型进行编号。如果我们再考虑修改后的对角函数

�(�)=��(�)+1

很容易看出这个函数也不能是原始递归的。因为如果 �(�) 与枚举中的某个函数 ��(�) 相重合，那么我们将得到 ��(�)=�(�)=��(�)+1，这是一个矛盾。请注意，这也表明，相对于这样的枚举，一元原始递归函数的通用函数 �1(�,�)=��(�) 本身不能是原始递归的，因为我们可以将 �(�) 定义为 �1(�,�)+1。Hilbert & Bernays (1939: ch. 5) 后来讨论了这一观察结果，并讨论了他们所谓的指称悖论——例如，参见 Priest 1997。

另一方面，有直观有效的程序来计算这些函数中的每一个。例如，对于 �(�) 的情况，我们可以按如下方式进行：

使用 � 构造 ��(�) 的定义；

通过执行相应的原始递归计算计算 ��(�) 的值；

加 1 并停止。

与 � 和 �1 的定义一样，上述程序在第 1.6 节讨论的意义上是有效的。但是，由于步骤 ii 中变量 � 的一致性，相应的函数不能通过单个原始递归定义来计算。因此，寻求扩展类 PR 的定义以涵盖此类函数的动机很自然。

实现这一点的一种方法是基于以下观察：有界最小化操作��(�→,�) 允许直接的算法表征——即，计算��(�→,�) 的值，依次检查�(�→,0)、�(�→,1)、…、�(�→,�)，… 给出输出�，并且只要�(�→,�) 成立就停止，如果在�=� 之前没有找到正实例，则停止�+1。这可以推广到所谓的无界搜索操作。具体而言，给定一个关系�(�→,�)，我们可以定义操作��(�→,�)，如果存在这样的�，则返回使�(�→,�) 最小的�，否则未定义。请注意，如果 �(�→,�) 是原始递归的，那么仍然可以通过连续检查 �(�→,0)、�(�→,1)……来有效地搜索 ��(�→,�) 的值。但由于没有事先指定上限，我们不能保证这个过程总是会终止。特别是，如果没有 �∈� 使得 �(�→,�) 成立，那么这个过程将无限期地继续下去。在这种情况下，我们规定 ��(�→,�) 未定义，由此可知 ��(�→,�) 将对应于所谓的偏函数——这一概念通过以下一系列定义得以精确化。

2.2.1 定义

所谓的偏递归函数类是从我们之前对 PR 的定义中获得的，通过在类似于 ��(�→,�) 的操作下闭合，该操作适用于函数而不是关系。为了定义此类，我们首先引入以下关于部分函数的约定，这些约定扩展了第 2 节开头给出的约定：

如果 �(�→) 对所有 �→∈�� 都有定义，则函数 �:��→� 被称为全函数。否则 �(�→) 被称为偏函数。

我们写 �(�→)↓ 来表示 �(�→) 在 �→ 处有定义，此外，如果 �(�→) 在 �→ 处有定义并且等于 �，则 �(�→)↓=�。否则，我们写 �(�→)↑ 来表示 �(�→) 在 �→ 处未定义。

�(�→) 的定义域是集合 dom(�)={�→∈��:�(�→)↓}。

我们写为 �(�→)≃�(�→) 以防所有 �→∈�， �(�→) 和 �(�→) 都未定义，或者都已定义且相等。

假设我们得到一个部分函数 �(�0,…,��−1,�)。我们现在引入形式为 ���(�0,…,��−1,�) 的项，定义如下：

(28)���(�0,…,��−1,�)={�如果 � 使得 �(�0,…,��−1,�)=0 并且 ∀�＜�(�(�0,…,�1,�)↓≠0)↑否则

换句话说，���(�→,�) 等于最小 � 使得 �(�→,�)=0 前提是存在这样的 � 并且 �(�→,�) 对于所有 0≤�＜� 都有定义但不等于 0。另一方面，只要不存在 � 使得 �(�→,�)=0，或者存在这样的 �，但对于某些 �＜�，�(�→,�) 未定义，则 ��(�→,�) 未定义。

由于此定义唯一地确定了���(�→,�)，因此 (28) 也可以被视为定义一个函数 Min�，它将 �+1 元偏函数映射到 k 元偏函数。我们现在定义函数 PartREC 和 REC 的类如下：

定义 2.5：偏递归函数 PartREC 类（也称为 �-递归函数）是类型为 ��→� 的偏函数的最小类，包含初始函数 �PR={0,�,���} 并在函数 OpPartREC={Comp��,PrimRec�,Min�} 下封闭。

如果 �∈PartREC，我们称函数 �:��→� 为偏递归。此外，如果 �∈PartREC 并且 � 是全递归，我们称 � 为递归。递归函数集将用 REC 表示。

由于自 1930 年代以来，“偏递归函数”这一名称就一直是表示此类的标准用法，因此我们将在此保留它。尽管如此，它至少在两个方面可能会造成混淆。首先，由于在断言“� 是偏递归函数”中，“偏”用于修饰“函数”而不是“递归”，因此更自然的表达方式是“递归偏函数”。其次，尽管名称如此，偏递归函数类包含全函数。具体而言，递归函数根据定义是偏递归的，同时也是全递归的。我们将在第 3.2 节中看到，也存在真正偏递归的偏递归函数和非递归的全函数。

最后请注意，如果 �(�→) 是递归的，则可以通过有限数量的组合、原始递归和无界最小化应用来定义，同时在其定义中保留中间函数的总体。因此，尽管 �(�→) 的规范可能涉及一个或多个无界搜索的应用，但计算其值所需的每个搜索都保证在有限步骤内终止。因此，REC 中的所有函数都可以通过算法计算（尽管我们很快就会看到此类包含非原始递归的函数）。这构成了 Church 论文的部分证据——即 REC 与有效可计算函数类相一致的主张——已在第 1.6 节中进行概述。

2.2.2 范式定理

一旦我们定义了 PartREC 类，自然就会出现一个问题，即是否所有部分递归函数都可以以规范方式定义。范式定理——最初由克莱尼 (1936a) 提出——通过证明一次应用无界最小化算子就足以获得所有这些函数，对这个问题给出了肯定的答案。为了表述这一结果，可以方便地将 � 运算符的应用正式扩展到原始递归关系 �(�→)，方式与本节开头讨论的方式相同——即

(29)���(�→,�)={最小 �，使得 �(�→,�)，如果存在这样的 �↑，否则

定理 2.3：对于所有 �∈�，存在一个 �+2 元原始递归关系 ��(�,�→,�)——即所谓的 Kleene T 谓​​词——和一个原始递归函数 �(�)（不依赖于 �），满足以下条件：对于所有 k 元偏递归函数 �(�→)，存在 �∈�，使得对于所有 �→∈��

�(�→)≃�(����(�,�→,�))

由于 ���(�→,�)≃���¬�(�→,�)，很容易看出，通过在 (29) 定义的操作下关闭原始递归函数，也可以获得类 PartREC 。因此，定理 2.3 的一个结果是，确实可以通过对关系 ��(�,�→,�) 应用一次无界搜索来定义任何 k 元偏递归函数 �(�→) 以选择 �。更一般地，范式定理说明了如何从单个关系 ��(�,�→,�) 定义任何此类函数，其中 � 的值用作 �(�→) 根据基函数 �PR 和操作 OpPartRec 定义的方式的描述。这样的�被称为�(�→)的索引。正如我们将在第 3 节中看到的，这种索引的可用性是部分递归函数的核心特征之一，这使得它们能够为可计算性和不可计算性的一般理论提供基础。

涉及定理 2.3 证明的完整细节。但基本思想可以总结如下：

每个部分递归函数�(�→)都由语言

0,�,���,Comp��,PrimRec�,Min�

上的术语�定义，其方式扩展了第 2.1.1 节末尾介绍的部分递归函数的符号方案。通过将该语言的原子表达式与自然数相关联，方式与第 1.3 节中描述的哥德尔编号 ⌜⋅⌝ 相同，然后采用第 2.1.2 节末尾描述的编码机制，就可以将 � 与自然数 ⌜�⌝=� 相关联，后者可以作为 �(�→) 的索引。

现在可以通过形式化以下决策算法来构造 ��(�,�→,�) 的定义：

在输入 �,�→,� 时，构造一个术语 �，从 � 定义 �(�→)；

将 � 理解为类似于计算 (17) 所示例的一系列中间计算步骤的潜在代码，检查 � 是否编码了对输入 �→ 的 len(�) 执行 � 描述的计算的方式之一；

如果是，则接受 - 即 ��(�,�→,�) 成立 - 如果不成立，则拒绝 - 即 ¬��(�,�→,�) 成立。

通过以这种方式对计算序列的代码进行无界搜索，我们实现了双重目的：既确定输入 �→ 时 � 描述的计算是否在有限步后停止，如果是，则还找到见证这一事实的计算序列的代码 �。 [22] 然后可以通过形式化从 � 编码的序列的最后一步 (�)len(�)−1 中提取计算输出的操作来定义函数 �(�)。 如果 ��(�,�→,�) 成立，则 �(�) 将对应于值 �(�→)。 由于上述步骤仅需要执行有界搜索并检查有限序列的局部组合性质，因此还可以证明 ��(�,�→,�) 和 �(�) 是原始递归的。

本证明中使用的技巧还可用于证明�(�,�)、通用 k 元原始递归求值函数 ��(�,�→) 和修改的对角函数 �(�) 都是递归的（尽管我们上文已经看到它们不是原始递归的）。例如，请注意，上文描述的 k 元部分递归函数定义的编码还允许我们通过考虑不包含 Min� 的项的代码来统一枚举所有原始递归函数 �0(�→)、�1(�→)、…。我们可以以这种方式定义一个原始递归函数 �(�) 并枚举这些函数的索引，从而我们可以得到 k 元原始递归函数的通用函数为 ��(�,�→)=�(���1(�(�),�→,�))=��(�→)。但请注意，由于 ��(�→) 始终有定义，�1(�,�→) 不仅是部分递归的，而且是完全递归的，因此是递归的。

考虑到第 1.6 节中总结的计算模型之间的等价性，还可以为那里提到的每个计算模型制定定理 2.3 的一个版本。例如，在图灵机模型 � 的情况下，范式定理的类似版本可用于证明存在一个单一的通用图灵机（参见图灵机条目）�，使得每个部分递归函数 �(�→) 对应于由 �(�,�→) 为某个 �∈� 计算的函数。图灵 (1937: sec. 6) 给出了这类证明，克莱恩 (1936a: sec. 2) 给出了一般递归函数 GR（另见克莱恩 1952: sec. 58），肖恩菲尔德 (1967: ch. 7.4) 给出了皮亚诺算术中可表示的函数类“PA”，卡特兰 (1980: ch. 5) 给出了无限寄存器机模型 �的完整证明。

3. 可计算性理论

可计算性理论是当代数理逻辑的一个子领域，致力于根据函数和自然数集的绝对和相对可计算性以及可定义性理论性质对其进行分类。该主题在起源和内容上都与递归函数的研究密切相关。这反映在可计算性理论从 20 世纪 30 年代诞生到 90 年代末一直被称为递归函数理论（或简称为递归理论）。这也反映在所谓递归定理的制定和证明中，该定理提供了递归可定义性和自指构造之间的基本联系，而自指构造是可计算性理论中许多方法的核心（见第 3.4 节）。

由于第 1.7 节中讨论的原因，当代对可计算性理论的阐述通常以抽象的方式呈现，力求尽量减少对计算模型的具体特征（例如部分递归函数）的引用。因此，有必要强调对第 1 节和第 2 节中使用的传统术语以及本节中将使用的更现代的术语的以下修改：

将使用表达式可计算函数和部分可计算函数来代替第 2.2.1 节中定义的传统术语递归函数和部分递归函数。

将使用表达式可计算集来代替传统术语递归集。同样，将使用可计算可枚举（或 c.e.）集来代替传统术语递归可枚举（或 r.e.）集（参见第 3.3 节）。

本节将保留第 2.1 节和第 2.2 节开头介绍的其他符号约定。

3.1 指数化、s-m-n 定理和普遍性

可计算性理论中第一个重要的结果是克莱尼 (1936a) 对范式定理的证明，该定理在第 2.2.2 节中提出。如该定理所述，范式定理可以理解为说明如何将每个 k 元偏可计算函数 �(�→) 与其称为其指数的自然数 � 相关联，使得 �(�→)≃��(��(�,�→,�))。这样的 � 可以被认为是由基函数、组合、原始递归和最小化构建的计算机程序的名称，通过它可以计算出值 �(�→) 。这也导致了所谓的 k 元偏可计算函数的索引化

�0�(�→),�1�(�→),�2�(�→),…,���(�→),…

其中 ���(�→)≃����(�,�→,�)。这种枚举提供了一种统一的方法，可以按索引顺序列出所有偏可计算函数。但应注意，每个偏可计算函数都有无数个索引。例如，给定一个由 ��(�→) 计算的函数 ��:��→�，可以定义无数个具有不同索引 ��′(�→),��″(�→),… 的外延重合函数——例如，通过“填充”由 �� 编码的定义，其中为每个 ��∈� 连续添加然后减去 ��。由于这给出了一个外延等价函数的定义，因此可以得出无穷多个���(�→)将对应于同一个外延函数。

与范式定理密切相关的结果是以下结果，通常称为s-m-n定理：

定理3.1：对于所有�,�∈�，存在一个原始递归函数���(�,�0,…,��−1)，使得

����(�,�0,…,��−1)�(�0,…,��−1)≃���+�(�0,…,��−1,�0,…,��−1)