递归函数（一）

递归函数是可计算性理论中研究的一类自然数函数，可计算性理论是当代数理逻辑的一个分支，最初被称为递归函数理论。此类函数的名称来自递归过程，通过递归过程，函数的值由应用于较小参数的相同函数定义。

可以通过考虑熟悉的阶乘函数 �! 来说明此过程——即，如果 �＞0，则返回乘积 1×2×…×�，否则返回 1。此函数的另一种递归定义如下：

(1)fact(0)=1fact(�+1)=(�+1)×fact(�)

这样的定义乍一看可能有点循环，因为左侧的 fact(�) 值是根据右侧的相同函数定义的。然而，递归定义的一个典型特征是，它们允许通过连续“展开” �＞0 的子句直到达到 �=0 的子句（所谓的基准情况）来计算它们描述的函数的值。例如，可以使用前面的定义计算出����(4)的值，如下所示：

(2)fact(4)=4×fact(3)=4×(3×fact(2))=4×(3×(2×fact(1)))=4×(3×(2×1×(fact(0))))=4×(3×(2×(1×1)))=24

这样理解，定义方程 (1) 提供了一种计算 fact(�) 的算法，即一种有效的计算其值的方法，可以由人或机械计算设备在有限的步骤内完成。正是出于这个原因，一类类似于 (1) 所举例的递归定义，即一般递归函数，首先被用作递归函数理论最初建立的计算数学模型。

本条目第 1 节概述了逻辑和数学的基础发展，这些发展导致了 20 世纪 30 年代递归函数理论的创立。第 2 节概述了不同形式的递归定义，包括对该主题的经典发展最为核心的原始递归函数和部分递归函数。第 3 节概述了可计算性理论，包括所谓的递归定理（第 3.4 节）——这一结果强调了递归对于一般计算的核心地位以及它与自指的关系。本条目的后续更新将概述证明理论和计算机科学中使用的子递归层次结构，以及对当代可计算性理论的更全面论述。

1. 历史背景

1.1 递归定义的早期历史

1.2 原始递归的起源

1.3 算术可表示性和哥德尔第一不完备定理

1.4 阿克曼-彼得函数

1.5 一般递归函数

1.6 丘奇论题

1.7 判定问题和不可判定性

1.8 递归函数理论和可计算性理论的起源

2. 递归的形式

2.1 原始递归函数 (PR)

2.1.1 定义

2.1.2 示例

2.1.3 原始递归函数的附加闭包属性

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

2.2.1 定义

2.2.2 范式定理

3. 可计算性理论

3.1 索引、s-m-n 定理和普遍性

3.2 不可计算函数和不可判定问题

3.3 可计算和可计算可枚举集

3.4 递归定理

3.5 可约性和度数

3.5.1 多一度数

3.5.2 图灵度数

3.6 算术和分析层次

3.6.1 算术层次

3.6.2 分析层次

4. 进一步阅读

参考书目

学术工具

其他互联网资源

相关条目

补充：阿克曼-彼得函数的历史

1. 历史背景

递归函数理论通常作为最初称为递归函数理论的学科历史的一章来介绍。这一主题的根源在于 20 世纪上半叶的基础性辩论。在这种背景下，需要对我们自然描述的归纳或递归推理模式进行精确分析，这些模式在数学公理理论的演绎机制中发挥着作用。本节将追溯这一历史，重点介绍不同形式的递归如何被理解为各种逐步算法过程的典范。

本节假设读者熟悉第 2 节和第 3 节中介绍的一些术语。建议读者从这里开始了解递归函数或可计算性理论的技术概述。

1.1 递归定义的早期历史

在古代和中世纪数学史中可以断断续续地找到递归定义的例子。一个熟悉的例子是斐波那契数列 ��，由递归 �0=1,�1=1 和 ��=��−1+��−2 给出（见第 2.1.3 节）。这个序列的定义传统上归功于 13 世纪意大利数学家列奥纳多·比萨（Leonardo of Pisa，又名斐波那契），他在他的《Liber Abaci》中以一个涉及人口遗传学的例子为背景引入了它（见斐波那契 1202 [2003: 404–405]）。但类似序列的描述也可以在公元前 700 年的希腊、埃及和梵文资料中找到（例如，见 Singh 1985）。

人们对递归作为一种函数定义方式的兴趣起源于 19 世纪中叶，当时正值更广泛的算术分析计划以及随后对算术本身基础的讨论。在这种背景下，数论函数递归定义的制定与数学归纳法作为一种自然数推理方式的孤立密切相关。正是在这种背景下，格拉斯曼 (1861) 和皮尔斯 (1881) 首次给出了人们熟悉的加法和乘法的递归定义：[1]

(3)i.�+0=�ii.�+(�+1)=(�+�)+1(4)i.�×0=0ii.�×(�+1)=(�×�)+�

然后他们使用这些定义来证明这些运算的结合律、交换律和分配律。[2]

第一个使用“递归定义”这一表述的人似乎是戴德金 (Dedekind)，他在他的论文《数论是什么，又是什么？》（1888 年）中提出了算术的集合论基础，其中戴德金证明了可以陈述和证明由原始递归定义的函数的存在性和唯一性作为数学定理 (§125-126)。他制定了加法 (§135)、乘法 (§147) 和指数运算 (§155) 的递归定义，然后通过归纳法正式证明如此定义的函数满足预期的代数恒等式。这些定义中的前两个后来被皮亚诺 (Peano) (1889 年) 采用，作为他基于戴德金专著的算术直接公理化中符号 + 和 × 的定义。

1.2 原始递归的起源

第一篇专门讨论递归可定义性的作品是 Skolem (1923) 的论文

初等算术的基础由递归思维模式建立，不使用范围无限的明显变量。

这项工作对于可计算性理论的后续发展具有重要意义，至少有三个原因。首先，它包含了我们现在所说的原始递归函数的非正式描述。其次，它可以被视为递归可定义性与有效可计算性联系在一起的第一个地方（另见 Skolem 1946）。第三，它表明，各种函数和关系都是原始递归的，其方式预示了 Gödel (1931) 使用原始递归进行语法算术化。

斯科勒姆的既定目标之一是为数论提供一个逻辑基础，避免使用无限制量词。在这方面，他受到以下观察的启发：有可能在不使用“总是”（即对所有）和“有时”（即存在）等表达式的情况下开发许多初等算术，这些表达式出现在罗素和怀特黑德在《数学原理》（1910-1913）中给出的数论形式中。这将通过将算术定理表述为他所称的函数断言来实现。这些采用由原始递归运算定义的项之间的恒等式的形式，斯科勒姆称之为描述函数。例如，加法的交换性可以用具有自由变量的方程式来表示

(5)�+�=�+�

如果在 Skolem 描述的系统中可以证明此类陈述，则其预期解释是该主张对所有自然数都普遍成立 - 例如，∀�∀�(�+�=�+�)。但在 Skolem 的系统中，没有办法否定这样的陈述来表达一个纯粹的存在性断言，而无需提供证据。

后来，Hilbert & Bernays (1934)（他们提供了第一本关于递归的教科书）将 (5) 之类的陈述称为可验证的，因为可以通过用具体数字替换变量来计算验证它们的单个实例。这是通过 Skolem 所称的“递归思维模式”实现的。这个短语的含义可以通过他描述的系统的以下属性来阐明：

自然数与后继函数�+1一起被视为基本对象；

假设被证明相等的描述函数可以在其他表达式中互相替代；

自然数上的所有函数和关系的定义都是通过递归给出的；

诸如 (5) 之类的函数断言必须通过归纳法来证明。

以这些原理为基础，斯科勒姆展示了如何获得前驱函数和减法函数、小于、可除性和素数关系、最大公约数、最小公倍数以及有界和与积的递归定义，这些定义与下面第 2.1.2 节中给出的类似。

总体而言，Skolem 考虑了我们现在称之为原始递归、值过程递归、双重递归和类型为 �→� 的函数递归的实例。然而，他并没有引入一般模式来系统地区分这些定义模式。尽管如此，Skolem 处理的 i-iv 性质提供了一种将 (2) 之类的计算同化为无量词一阶逻辑中的推导的方法。因此，在 Skolem (1923) 中不难辨别出我们现在称为原始递归算术的系统的核心（后来由 Hilbert & Bernays 1934：第 7 章正式引入）。

递归函数一般理论发展的下一个重要步骤是希尔伯特纲领与哥德尔 (1931) 对不完备性定理的证明相互作用的结果。希尔伯特 (1900) 曾宣布，在集合论悖论面前，要证明算术的一致性，最终也证明分析和集合论的一致性。他在 20 世纪 10 年代至 20 年代的一系列讲座和演讲中描述了进行此类证明的初步计划，这些讲座和演讲描述了后来被称为有限观点的内容，即关于有限组合对象的数学推理片段，旨在作为一致性证明的安全基础。证明本身将使用希尔伯特所说的元数学的方法进行，即对公理和推导的正式研究，它将发展成为现在称为证明理论的学科。

在对该计划的初步描述之一中，希尔伯特 (1905) 勾勒出了一致性的元数学证明可能采用的基本形式。例如，假设�是一个数学理论，可以证明以下条件：

如果�将推理规则应用于系统的公理�不会导致矛盾，那么�+1 个应用也不会导致矛盾。

如果可以提供 i) 的数学证明，似乎可以得出结论

�是一致的。

然而，庞加莱 (1906) 观察到希尔伯特的方法依赖于数学归纳法从 i 推断出 ii。他反对的理由是，如果所讨论的系统�本身包含了旨在形式化归纳法的原理，那么这使得希尔伯特提出的方法陷入循环。[3]

希尔伯特与他的合作者阿克曼和伯内斯在 1910-1920 年代极大地发展了元数学。这成为希尔伯特 (1922) 演讲的基础，他在演讲中回应了庞加莱，系统地区分了对象语言中数学归纳法的“形式”出现和归纳法的元理论使用，归纳法是一种“内容” [inhaltliche] 原则，用于推理有限组合对象的证明。正是在这种背景下，希尔伯特将后一种形式的归纳法与“数字符号的构造和解构”联系起来 (1922 [1996: 1123])。

正如在随后的演讲中明确指出的那样，希尔伯特将“数字符号”理解为以笔划符号形式书写的一元数字

|,||,|||,…

可以通过连接或删除笔划来具体操作此类表达式，其方式反映了斯科勒姆“递归思维模式”中后继和前继的算术运算。这一观察反过来又为希尔伯特对 (5) 等函数断言含义的解释提供了依据，即它们可以从递归定义中逻辑推导出来，而递归定义也充当着计算它们所定义函数值的程序 (Hilbert 1920 [2013: 54–57])。

希尔伯特于 1923 年首次描述了有限数论的逻辑演算，包括“有限总体的递归和直观归纳”([1996: 1139])。[4] 虽然这次演讲也包括对同时递归定义的讨论，但对他现在所认识的递归方案的更广泛的讨论在他著名的论文“论无限”(1926)中进行了讨论。这包括对希尔伯特所说的普通递归(类似于斯科勒姆对原始递归的描述)、超限递归以及更高类型的递归的讨论。 （这些不同形式的递归将在 Ackermann-Péter 函数的补充中进一步讨论。）这种处理方式清楚地表明，希尔伯特和他的合作者已经朝着发展递归可定义性的一般理论迈出了实质性的一步。然而，最终，由于哥德尔很快提供的更精确的原始递归公式，希尔伯特的演讲的影响力被削弱了。[5]

哥德尔（1931 [1986：157–159]）的定义如下：

如果

(6)i.�(0,�2,…,��)=�(�2,…,��)ii.�(�+1,�2,…,��)=�(�,�(�,�2,…,��),�2,…,��)

对所有�2,…,��,�都成立，则数论函数�(�1,…,��) 被称为根据数论函数�(�1,�2,…,��−1) 和 �(�1,�2,…,��+1) 递归定义的。

如果存在一个有限数论函数序列�1,�2,…��，该序列以�结尾，并且具有这样的性质：序列中的每个函数��都根据前面的两个函数递归定义，或者通过替换由前面的任何一个函数得出，或者最终是常数或后继函数�+1…，则称数论函数�为递归函数。如果存在一个递归函数�(�1…,��)，使得对于所有�1,�2,…,��，则称自然数之间的关系�(�1,…,��)为递归函数

(7)�(�1,…,��)↔�(�1,…,��)=0

抛开哥德尔使用的术语“递归”而不是“原始递归”（将在下文解释），这一论述与第 2.1 节中给出的原始递归函数的当代定义几乎一致。[6] 哥德尔的定义还改进了他的前辈的定义，明确定义了原始递归定义中允许的初始函数类，并指出每个原始递归函数都具有一个函数序列定义，该定义显示了它是如何从初始函数构建起来的。这清楚地表明，原始递归函数构成了自然数上数学上定义明确的函数类（这里将其表示为 PR）。哥德尔还证明了原始递归关系（通过 (7) 定义为特征函数）在由原始递归函数界定的命题运算和量化下是封闭的（参见第 2.1.2 节）。

1.3 算术可表示性和哥德尔第一不完备性定理

上述定义出现在哥德尔著名的 (1931) 论文“论数学原理及其相关系统的形式上不可判定命题 I”中。正如他在介绍之前所观察到的，原始递归的定义实际上是论文主要焦点的题外话——即证明他称之为�的算术公理系统的不完备性。为了理解哥德尔对递归函数理论最初发展的贡献，关注该系统的一些特征以及他对第一不完备性定理本身的证明将大有裨益。 （更多细节和背景信息请见哥德尔不完备定理条目。）

系统�是从怀特海和罗素的《数学原理》（1910-1913）中得到的，通过省略类型的分支，将自然数作为最低类型，并为它们添加二阶皮亚诺公理。因此，它是一个固定的形式系统，具有有限多个非逻辑公理，足以发展初等数论。[7]还记得，如果一个算术系统不能证明每个自然数 �∈� 的 ∃��(�) 和 ¬�(�―)（其中 �―=df�(�(…�(0))) n 次），则称其为 �-一致的，并且 �-一致性意味着简单一致性（即公式及其否定的不可导性）。

哥德尔证明的不完备定理指出，如果 � 是 ω-一致的，则存在一个公式 ��，它在 � 中是不可判定的——即从其公理既无法证明也无法反驳。为了获得这样的公式，哥德尔首先证明了如何通过一种被称为句法算术化的技术将�-公式和证明的各种句法和元理论性质表示为原始递归关系（参见词条哥德尔不完备定理）。其次，他证明了对于每个原始递归关系 �(�1,…,��) 都存在一个 � 的“类符号”（即公式） ��(�1,…,��)，使得 �(�1,…,��) 对给定的数组 �1,…,�� 成立（或不成立）这一事实反映在 � 中，当正式数字 �―=�(�(…�(0))) (n 次) 代替 �� 时，��(�1,…,��) 的对应实例 � 的可证明性（或可反驳性）也反映在 � 中——即

(8)i.如果 �(�1,…,��)，则 �⊢��(�―1,…,�―�)ii.如果 ¬�(�1,…,��)，则 �⊢¬��(�―1,…,�―�)

根据哥德尔后来在 1934 年引入了这一术语，在这种情况下，��(�1,…,��) 表示 �(�1,…,��)。在这次演讲中，他还推广了他之前的定义，即函数 �(�1,…,��) 可在 � 中表示，只要存在一个公式 ��(�1,…,��,�)，并且对于所有 �1,…,��,�∈�，

(9)�(�1,…,��)=� 当且仅当 �⊢��(�―1,…,�―�,�―)

哥德尔的语法算术化提供了一种根据其句法结构为每个原始符号、术语、公式和证明�分配一个唯一的哥德尔数 ⌜�⌝∈� 的方法。这种技术利用了一个熟悉的观察，即有限数字序列�1，…，�可以编码为素数幂2�1⋅3�2⋅…����的乘积，从而可以证明序列上的各种相关运算都是原始递归的，例如，采用两个数字�和�编码序列并返回连接�后跟�的结果的代码�∗�的运算。哥德尔在此基础上继续证明，关于�的语法和证明理论的一系列概念是原始递归的，例如，返回由�编码的公式否定的哥德尔数的函数Neg(�)可以定义为⌜¬⌝∗�。因此，相关递归定义的可用性自然而然地就出来了，因为像合式公式这样的句法概念的归纳定义概括了希尔伯特所描述的“数符号的构造和解构”。[8]