递归函数（二）

哥德尔列表中的倒数第二个定义是关系证明�(�,�)，它在一个�-公式�的哥德尔数和�-公式�1,…,��的有限序列的哥德尔数之间成立，只要后者是从�的公理正确形成的前者的推导——即

证明�(⌜�1,…,��⌝,⌜�⌝)) 当且仅当�⊢�通过�1,…,��的推导进行，其中每个��要么是�的公理，要么通过其推理规则从先前的公式得出。

从 (8) 可知，存在一个公式 Prf�(�,�)，表示 Proof�(�,�)，因此也存在一个公式

Prov�(�)=df∃�Prf�(�,�)。

哥德尔将后一个公式命名为 bew(�)（代表 beweisbar），因为它可以理解为表示存在一个由哥德尔数为 � 的公式的 � 的公理证明。但与定义中出现的表示原始递归关系的其他公式不同，Prov�(�) 包含一个无界的存在量词。因此，正如哥德尔仔细观察到的那样，没有理由期望它定义了一个原始递归关系。

然而，哥德尔使用这个公式构造了一个在 � 中不可判定的句子。这可以通过应用所谓的对角引理（参见哥德尔不完备定理）来实现，该引理指出，对于 � 的每个公式 �(�)，都存在一个句子 �� 使得

�⊢��↔�(⌜��⌝―)

当应用于公式 ¬Prov�(�) 时，对角引理会得出一个句子 ��——即 � 的所谓哥德尔句子——使得 �⊢��↔¬Prov�(⌜��⌝)。因此 �� 可以解释为“自说自话”，即它在 � 中是无法证明的。哥德尔表明这个公式具有以下属性：

如果 � 是一致的，则 �⊬��；

如果 � 是 ω 一致的，则 �⊬¬��。

这构成了现在所谓的哥德尔第一不完备定理。

这一事实的证明明确依赖于关系证明�(�,�)在�中的可表示性，而这又源于其原始的递归性。但是，哥德尔证明所依赖的技术也以其他几种方式促进了可计算性理论的后续发展。首先，从哥德尔对�公式进行编号的可能性可知，我们也可以有效地将它们枚举为�0(�)、�1(�)、�2(�)，……——例如，按⌜��⌝的递归顺序排列。这提供了一种通过公式索引来引用公式的机制，而这又为克莱尼 (1936a) 在范式定理证明中使用类似的一般递归定义索引提供了一个重要的先例（见第 2.2.2 节）。其次，对角线引理的证明还展示了如何形式化地替换自由变量的项，从而得到康托对角线论证的有效形式（参见自指条目）。这种技术为在诸如停机问题的不可判定性（图灵 1937，参见第 3.2 节）、递归定理（克莱恩 1938，参见第 3.4 节）和层次定理（克莱恩 1943，参见第 3.6 节）等结果中使用对角线化提供了一个重要的先例。

哥德尔论文的另一个重要贡献在于，在证明了�的不完备性之后，他采取了一些步骤来分离公理理论的特征，这些特征足以确保它们满足类似的不可判定性结果。除了足够强大以满足（8）之外，他确定的另一个要求是“公理类和推理规则......是递归可定义的”（1931 [1986: 181]）。他指出，相对于其公理的适当哥德尔编号，这些特征既包含策梅洛-弗兰克尔集合论[ZF]，也包含类似于我们现在称为一阶皮亚诺算术[PA]的一阶算术系统。具体而言，虽然这两个系统都不是有限公理化的，但它们可以通过有限数量的方案（例如，归纳或理解）公理化，使得关系⌜�⌝是T公理的哥德尔数是原始递归的。 正是因为所讨论的方案中的成员资格由公式上的归纳条件决定，而公式的结构与原始递归定义的结构相似。

这一观察为哥德尔随后在讲座（1934 年）中重新审视不完备性定理奠定了基础，他在讲座中对他最初（1931 年）的递归性定义进行了重要的概括。 哥德尔首先对刚刚描述的理论的要求进行了以下非正式描述：

我们要求推理规则以及有意义的公式和公理的定义是建设性的；也就是说，对于每条推理规则，都应有一个有限的程序来确定给定公式�是否是给定公式�1，…，�的直接结果（根据该规则），并且应有一个有限的程序来确定给定公式�是有意义的公式还是公理。（Gödel 1934：346）

他还明确表示，他所谓的“递归性”最初应被视为一个非正式的概念，他正试图将其精确化：

递归函数具有重要的特性，即对于给定的参数值的每个集合，函数的值都可以通过有限的过程计算出来。类似地，递归关系（类）是可判定的，因为表示函数是可计算的，所以对于每个给定的 n 元组自然数，都可以通过有限的过程确定关系是否成立（数字是否属于该类）。 （Gödel 1934 [1986: 348]）

因此，Gödel 的目标之一是提供“递归”一词的数学定义，该定义在某种程度上概括了先前的递归可定义性示例，但也尽可能地捕捉了可通过有限过程计算的函数类。这导致他定义了所谓的 一般递归函数 （见 第 1.5 节），而该函数的分离反过来在 Church 论文 的制定中发挥了重要作用（见 第 1.6 节）。然而，Gödel 的定义也是在其他工作的背景下进行的，这些工作受到希尔伯特对不同形式递归定义的最初考虑的启发。现在研究这些发展将很有用。

1.4 Ackermann-Péter 函数

早在 (1926) 时，希尔伯特就已预见到可以制定函数定义，这些函数的值可以以递归方式计算，但本身不是原始递归的。为了说明如何获得这样的定义，他提出了一个启发式论证，涉及以下函数序列：

⋰�0(�,�)=�+1(后继)�1(�,�)=�+�(加法)�2(�,�)=�×�(乘法)�3(�,�)=��(幂)�4(�,�)=��⋰�⏟� 次(超幂)⋮

此序列中的函数定义为 ��+1(�,�+1) 可通过原始递归获得，即 ��(��+1(�,�),�)，以及适当的基准情况。因此，考虑函数

(10)�(�,�,�)=��(�,�)

是有意义的，其第一个参数 � 表示函数 ��(�,�) 在先前列表中的位置。对于固定的 �,�,�∈�，因此可以通过首先构造 ��(�,�) 的定义然后在 �,� 处对其进行求值来有效地计算 �(�,�,�) 的值。但也很容易看出，对于足够大的 �，��+1(�,�) 最终将优于 ��(�,�)。这反过来表明 �(�,�,�) 不能通过有限次数的原始递归方案应用来定义。因此，�(�,�,�) 本身不是原始递归的。

刚刚给出的 �(�,�,�) 的规范不具有递归定义的形式。但是，可以以一种概括方案 (6) 格式的方式定义类似的函数。这样做的一种方法是使用 Skolem 和 Hilbert 都考虑过的更高类型的简单递归形式。为此，考虑迭代函数 Iter，它以函数 �:�→� 和自然数 � 作为参数，并返回作为 � 与自身的 i 重组合获得的函数。换句话说，Iter 的类型为

(�→�)→(�→(�→�))。

此类函数可正式定义如下：

Iter(�,0)=��Iter(�,�+1)=Comp(�,Iter(�,�))

此处 �� 表示恒等函数（即 ��(�)=�），

Comp(�,Iter(�,�))

表示我们更习惯表达为 �∘��——即

�∘�∘…∘�⏟� 次

或 � 与 �� 组合的结果。

我们现在可以定义一个函数 �，它以自然数为输入并返回类型为 �→� 的函数——即类型为 �→(�→�)——如下所示：

�(0)=�+1 （即后继函数）�(�+1)=Iter(�(�),�)(�(�)(1))

由于 �(�) 的值是一个函数，因此这里 �+1 和

Iter(�(�),�)(�(�)(1))

都应理解为依赖于隐式抽象的变量 � 的 �→� 类型函数。换句话说，如果我们采用 �-演算的符号，那么我们应该将这些术语视为抽象的 ��.�+1 和

��.Iter(�(�),�)(�(�)(1))。

有了这些定义，现在可以验证，当�随�变化时，�(0),�(1),… 对应于以下增长率递增的函数序列：

⋰�(0)=��.�+1,�(1)=��.2+(�+3)−3=�+2,�(2)=��.2×�−3,�(3)=��.2�+3−3,�(4)=��.22⋰2⏟� times−3,⋮

这提供了一种定义现在通常称为 Péter 函数（或 Ackermann-Péter 函数）的方法，即 �(�,�)=��.�(�)(�)。 �(�,�) 具有与 ��(�,�) 相同的增长阶，并且可以通过上述论证证明 �(�,�) 不是原始递归的（参见，例如，Péter 1967：第 9 章）。

与函数系列 ��(�,�) 一样，很明显每个函数 �(�,�) 对于每个具体数字 �都是有效可计算的。然而，为了统一定义这个函数，我们必须使用函数 Iter 来定义 �，而函数 Iter 本身由类型 �→� 上的递归定义。因此出现了一个问题，即是否也可以通过自然数本身的递归形式来定义外延等价函数。

Ackermann (1928a) 对补充中描述的稍微复杂的 Ackermann 函数给出了肯定的回答，Péter (1935) 也直接对函数 �(�,�) 给出了肯定的回答。具体来说，可以通过 Ackermann 最初称为同时递归的方式制定与 �(�) 外延一致的函数定义，如下所示：[9]

(11)�(0,�+1)=�+1�(�+1,0)=�(�,1)�(�+1,�+1)=�(�,�(�+1,�))

此定义中的第三子句根据 �(�,�) 定义 �(�+1,�+1) 的值，其中 � 由 �(�+1,�) 的值决定。因此，定义 (11) 描述了一种计算 �(�,�) 值的算法，该算法总是以计算 (2) 所示的方式终止，这一点可能不是显而易见的。但请注意，当我们展开此定义右侧的子句时，要么 � 减少，要么 � 保持不变而 � 减少。因此，每次 � 达到 0 时， � 都会开始减小，最终达到基准情况。因此，尽管 �(�,�) 的值增长非常迅速（例如 �(4,3)=2265536−3），但仍有理由认为 (11) 满足哥德尔的要求，即递归定义的函数可以通过有限过程计算。

Péter (1932) 发起了对以 (11) 为例的此类替代递归方案的系统考虑。她还引入了“原始递归”一词来描述哥德尔方案 (6) 给出的函数类，这一选择在克莱恩 (1936a) 采用后成为标准。彼得还表明，原始递归函数是封闭的值递归过程（参见第 2.1.3 节）、多重递归和一个变量的嵌套递归（参见补充）。因此，不应将“原始”一词的选择理解为降低原始递归函数类的丰富性。相反，它标志着这样一个事实：像 (11) 这样导致更复杂的计算过程的定义也从他们的研究一开始就被希尔伯特、阿克曼和彼得等理论家视为“递归的”。

彼得在 1930 年代的工作也促成了她的著作（Péter 1967），其德文原版《递归函数》（Rekursive Funktionen）（1951）是第一本专门讨论递归函数的专著。这些发展与 Grzegorczyk（1953）后来的工作一起，启发了对各种子递归层次结构的研究，这些层次结构后来在证明理论和计算机科学中发挥了作用。[10]

1.5 一般递归函数

1934 年，哥德尔讨论递归的直接来源不是阿克曼或彼得的作品，而是与赫尔布兰德的私人交流，赫尔布兰德在之前的两篇论文（1930 年、1932 年）中提出了一种相关的推广递归定义的方法。哥德尔对赫尔布兰德建议的非正式描述如下：[11]

如果�表示未知函数，�1,…,��是已知函数，并且�和�以最一般的方式相互代换，并且得到的某些表达式对相等，那么，如果得到的函数方程组对�有且只有一个解，�就是递归函数。 （Gödel 1934 [1986: 308]）

为了举例说明，请考虑以下方程组：

(12)�(0)=0�(�)=�(�)+1�(�+1)=�(�)+1

在这种情况下，用 �(�) 表示的“未知”函数以辅助函数 �(�) 的形式指定，使得 �(�) 只在方程的左侧出现一次（除基本情况外）。尽管如此，这样的方程组与原始递归定义不同，因为它没有指定一种通过“解构”� 来确定性方式计算 �(�) 值的唯一方法，如 (2) 等计算所示。

在一般情况下，确实不能保证存在满足这种定义的唯一外延函数。但在这个例子中，可以证明 2×� 是方程组 (12) 中满足 �(�) 的唯一�→� 类型函数。这可以通过考虑以下计算�(2)来说明：

(13)i.�(2)=�(1)+1ii.�(1)=�(1)+1iii.�(1)=�(0)+1iv.�(0)=�(0)+1v.�(0)=0vi.�(0)=0+1vii.�(1)=(0+1)+1viii.�(1)=((0+1)+1)+1ix.�(2)=(((0+1)+1)+1)+1 (=4)

正如哥德尔所指出的，这种计算可以理解为无量词一阶逻辑中的推导，其中唯一允许的规则是用数字代替变量，并用已经导出相应恒等式的数字替换等式右边的项。

哥德尔引入了术语“一般递归”来描述以这种方式定义的函数。根据 Odifreddi (1989: ch. I.2) 的现代化表述，该类可根据以下初始定义指定：[12]

定义 1.1

数词类是包含 0 且在后继函数 �↦�(�) 下封闭的最小集合。我们将数词 �(�(…�(0))) n 次写为 �―。

项类是包含数词、变量 �0,�1,… 且在运算 �↦�(�) 和 �1,…,��↦���(�1,…,��) 下封闭的最小集合，其中 �,�1,…,�� 是项，��� 是原始 n 元函数符号。

如果�和�为项，且�的形式为���(�1,…,��)，其中�1,…,��不包含除�之外的任何函数符号，则�=�为方程。

方程组是一组有限方程。�(�1,…,��,�→)将用于表示包含基本函数符号�1,…,��和�→=�1,…,��之间的变量的方程组。

Herbrand (1932) 对数论函数�由方程组�(�1,…,��,�→)定义的含义进行了语义描述，要求系统有解，并且�与对每个解确定为�1的函数相一致。他还建议应该直观地证明这一事实，这反过来可以被认为是产生了一种计算�值的有效程序。[13] 然而，他并没有指定一个应该进行这种证明的正式系统。因此，哥德尔（本质上）建议对赫尔布兰德的定义进行以下句法替换：

定义 1.2：如果存在方程组 �(�1,…,��,�→)，并且如果 �� 是 � 的最后一个方程中最左边的函数符号，则对于所有 �1,…,��,�∈�

�(�1,…,��)=�

当且仅当方程 ��(�―1,…,�―�)=�―

可以通过以下两个规则从包含 � 的方程中推导出来，则函数 �:��→� 是广义递归的：

R1：用数字替换方程中每个特定变量的出现。R2：如果 ��(�―1,…,�―�)=�― 已经导出，则 ��(�―1,…,�―�) 可以在 � 的方程中用数字 �― 替换等式的右边。

在这种情况下，我们说 � 定义 � 相对于 ���。

可以验证，上面展示的方程组 (12) 和推导 (13) 满足前述要求，从而说明了如何使用一般递归方程组进行机械计算。然而，某些系统——例如，{�(�)=0,�(�)=�(0)}——是不一致的，因为它们不被自然数上的任何函数满足，而其他系统——例如，{�(�)=�(�)}——不是唯一满足的。因此，哥德尔对一般递归性的定义的一个明显缺点是，没有明显的方法来确定给定的方程组 � 是否确定一个唯一的函数（即使只是部分定义）。这就是为什么在随后的可计算性理论发展中，哥德尔的刻画被其他外延等价定义（如克莱尼的部分递归函数（见第 2.2 节））取代的原因之一。

1.6 丘奇论题

通过定义 1.2 形式化他对递归性的非正式刻画，哥德尔成功地制定了一个定义，该定义包含了原始递归方案 (6)、阿克曼-彼得函数的定义以及希尔伯特考虑的其他几种方案。因此，哥德尔对一般递归性的定义还定义了一个 ��→� 类型的函数类 GR，它正确地包含了原始递归函数 PR。此外，我们现在知道，在�（事实上在更弱的算术系统中）中可表示的函数类不是原始递归函数，而是一般递归函数。将形式系统公理集（哥德尔数）的假设弱化为要求它们是一般递归而不是原始递归，从而确实提供了哥德尔设想的第一不完备定理的概括。

GR 的定义也具有历史重要性，因为它是最初称为递归函数但现在通常称为可计算函数的几个等效（且几乎同时）定义中的第一个（参见第 2.2 节）。这些发展还促成了在可计算性理论作为一门独立学科开始之前递归可定义性研究的两个最后章节之一——即现在称为 Church 论文的分离和最终采用。

丘奇的论点对应于这样的主张：可通过有限机械程序计算的函数类（或按传统说法，有效可计算）与一般递归函数类相吻合，即

(CT)�:��→� 当且仅当 �∈GR 时才有效可计算。

作者对 CT 旨在分析的有效可计算函数概念的解释存在一些历史差异。（有关这一点的更多信息，请参阅丘奇的论点和计算复杂性理论的条目。）尽管如此，人们普遍认为这个概念近似于通过算法计算的函数，并且正确理解该论点要求必须非正式地理解后一个概念。 [14]

从这个角度来看，哥德尔似乎早在 1934 年就提出了丘奇论题的一个版本。然而，在丘奇第一次明确阐述它时，他并没有立即认可它。[15]  由于周围的历史很复杂，记录以下观察作为第 2 节和第 3 节的前奏将很有用。[16]