复旦大学：《数理逻辑》课程教学资源（讲义）第7章递归论基本知识.pdf_大学文库

第 7 章递归论的基本知识递归论是递归函数论的简称。它数理逻辑的一个重要分支，由于递归函数是直观上的可计算函数的精确化，递归论也被称为可计算性理论。递归论创立于 1930 年代，最初是为了精确定义可计算性（即可判定性），有了可计算性（可判定性）的精确定义，人们才可以证明什么是不可计算的或不可判定的。很多经典的不可判定性结果，如停机问题和一阶逻辑的普遍有效性都是不可判定的，都是在 1930 年代建立的。之后人们的注意力转向了各种相对可计算性和由此产生的（不可解）度的研究。递归论的现代口号是研究可定义性，因为可定义性是可计算性的一种自然推广。依照对可定义性要求苛刻程度的大小，递归论的研究范围包括：（部分）理论计算机科学，古典递归论（一阶算术），（部分）描述集合论和（部分）集合论。还有各类高等递归论等等。我们介绍递归论的动机除了了解可计算性概念之外，在系统内“表示”递归关系也是证明哥德尔不完全性定理的重要组成部分。第 1 节原始递归函数 7.1.1 原始递归函数的定义定义 7.1. 以下三类函数称为初始函数：零函数 Z(x) = 0，后继函数 S(x)，和投射函数 π n i (x1, · · · , xn) = xi，其中 n 为正整数且 1 ≤ i ≤ n。令 n 为自然数，且 g : N n → N 和 h : N n+2 → N 分别为 n- 元和 (n + 2)-元函数。我们称 (n + 1)-元函数 f : N n+1 → N 为从 g 和 h 经原始递归得到的，如果 f(x1, · · · , xn, 0) = g(x1, · · · , xn), 且 f(x1, · · · , xn, y + 1) = h(x1, · · · , xn, y, f(x1, · · · , xn, y))。（注意：这里的 y + 1 实际上是 y 的后继 S(y)，严格地说，并不是加法。）为方便起见，我们规定一个 0-元函数 g 就是一个固定常数 c，这样一元函数 f 也可以像上面一样从 g 和 h 经原始递归得到： f(0) = c, 且 f(y + 1) = h(y, f(y))。 (7.1) 1

第 1 节原始递归函数第 7 章递归论的基本知识定义 7.2. 全体原始递归函数的集合 C 是最小的满足下列条件的集合: (1) 所有的初始函数都在 C 中。 (2) C 对函数复合封闭，即，如果 f(x1, · · · , xn) = g(h1(x1, · · · , xn), · · · , hr(x1, · · · , xn))，并且 g(y1, · · · , yr) 和 hi(x1, · · · , xn) （1 ≤ i ≤ r）都在 C 中，则 f 也在 C 中。 (3) C 对原始递归封闭。我们称 C 中的元素为原始递归函数。在第 ?? 章第 ?? 节中我们讨论过关于闭包的“自上而下”和“自下而上”的定义方式，并且论证了它们是等价的。定义 ?? 是“自上而下”的，换成“自下而上”的等价形式，我们有：每个原始递归函数 f 都有一个有穷的生成序列：⟨f1, f2, · · · , fn⟩，其中 fn = f 并且对任意 1 ≤ i ≤ n，fi 或者是初始函数，或者是由前面的函数通过复合或原始递归得到的。注意生成序列是不唯一的。我们可以沿着生成序列做归纳。例如，我们可以证明所有的原始递归函数都是全函数，即，如果 f : N n → N 是原始递归的，则 domf = N n（练习）。此外，也请大家思考一下所有的原始递归函数的确都是直观上可计算的。例 7.1. 自然数的加法是原始递归的。通常是利用后继函数由下列递归方程定义的： x + 0 = x, x + (y + 1) = S(x + y)。作为例子，我们给出它的一个生成序列：（今后我们将只给递归方程，而将生成序列留给对方程有疑义的读者。） S(x1) （后继函数），π 1 1 (x1) = x1 （一元投射函数），π 3 3 (x1, x2, x3) = x3 （三元投射函数），g(x1, x2, x3) = S ◦ π 3 3 (x1, x2, x3) = S(x3) （第一项与第三项的复合），f(x1, x2) （由第二项和第四项经原始递归得到） f(x1, 0) = π 1 1 (x1); f(x1, y + 1) = g(x1, y, f(x1, y))。显然，f(x, y) = x + y。引理 7.1. 下列函数都是原始递归的： 1. 常数函数 C n k (x1, · · · , xn) = k，其中 k 是一个固定的自然数。 2. 乘法函数 x · y、指数函数 x y 和阶乘函数 x!。 2

第 7 章递归论的基本知识第 1 节原始递归函数我们用符号 X := Y 表示 X 是按照 Y 来定义的，或按照 Y 定义的那个 X。引理 7.7. 假定 P(⃗x, z) 是一个原始递归的谓词。则 (a) 谓词 E(⃗x, y) := (∃z ≤ y)P(⃗x, z) 和 A(⃗x, y) := (∀z ≤ y)P(⃗x, z) 都是原始递归的。 (b) 函数 f(⃗x, y) := (µz ≤ y)P(⃗x, z) 也是原始递归的。证明: (a) 根据定义，我们有：谓词 (∀z ≤ y)P(⃗x, z) 为真当且仅当 ∏ z≤y χP (⃗x, z) = 1；并且谓词 (∃z ≤ y)P(⃗x, z) 等价于 ¬(∀z ≤ y)¬P(⃗x, z)。由此可以得到 (a)。 (b) 只须注意 (µz ≤ y)P(⃗x, z) = ∑y z=0 ∏z r=0 χ¬P (⃗x, r) 即可。特别注意当满足条件的 z 不存在时，等式右边恰恰等于 y + 1。 7.1.3 编码我们下面讨论一些有关素数的可计算性，目的是利用素数分解定理来编码。引理 7.8. (1) 谓词“x 整除 y”是原始递归的。 (2) 谓词“x 是合数”和“x 是素数”都是原始递归的。 (3) 函数 p(n) := 第 n 个素数是原始递归的。这个函数我们今后经常会用到。p(n) 也常被写作 pn，例如，p0 = 2, p1 = 3, p2 = 5, · · · 等等。证明: 练习。我们现在可以利用素数分解定理来能行地编码了。定义 7.4. (1) 我们用尖括号 ⟨a0, · · · , an⟩ 来表示乘积 p a0+1 0 · · · · · p an+1 n ，并把它称为有穷序列 (a0, · · · , an) 的哥德尔数。定义空序列 ⟨ ⟩ 的哥德尔数为 1。 (2) 定义函数 lh : N → N 为 lh(a) = µk ≤ a (pk - a)。我们称 lh(a) 为长度函数，因为 lh(1) = 0 且对于任意的哥德尔数 a = ⟨a0, · · · , an⟩，都有 lh(a) = n + 1。 (3) 定义关于 a 和 i 的二元函数 (a)i = µk ≤ a [p k+2 i - a]。我们称 (a)i 为分量函数，因为它刚好从编码为 a 的有穷序列中挑出第 i 项：对任意的哥德尔数 a = ⟨a0, · · · , an⟩， (a)i = ai（0 ≤ i ≤ n）。 (4) 对自然数 a, b 定义串接函数 a^b 如下： a^b = a · ∏ i<lh(b) p (b)i+1 lh(a)+i。 5

第 2 节递归函数第 7 章递归论的基本知识注意：函数 lh(a) 和 (a)i 都是全函数。特别地，函数 lh 对不是哥德尔数的自然数 a 也有定义，只不过我们不关心它的值罢了。对函数 (a)i 当 i ≥ lh(a) 时，情形也一样。引理 7.9. (1) 全体有穷序列的哥德尔数构成的集合是原始递归的。 (2) 函数 lh(a) 和 (a)i 都是原始递归的。 (3) 函数 a^b 是原始递归的且 ⟨a0, · · · , an⟩^⟨b0, · · · , bm⟩ = ⟨a0, · · · , an, b0, · · · , bm⟩。还有，如果 a 和 b 都是某个有穷序列的哥德尔数，则 a^b 也是。证明: 习题。回忆一下原始递归的定义，当我们定义 f(y + 1) 的时候，我们仅仅用到了 f 在前一点的值 f(y)。大家很自然地会猜测，我们并不非得要用前一点的值，只要我们以前已经算过的值我们应该都可以用，即，在定义 f(y + 1) 时，我们可以利用任何 f(z) 的值，只要 z ≤ y 即可。下面的引理说的就是这件事情。首先引入两个自然的术语。对任何一个全函数 f : N k+1 → N，令 F(⃗x, n) = p f(⃗x,0)+1 0 p f(⃗x,1)+1 1 · · · p f(⃗x,n)+1 n 。我们称它为 f 的历史函数。我们称函数 f 为从 g 和 h 经强递归得到的，如果 f(⃗x, 0) = g(⃗x); f(⃗x, y + 1) = h(⃗x, y, F(⃗x, y))。引理 7.10. 如果函数 f 为从 g 和 h 经强递归得到的，且 g 和 h 都是原始递归的，则 f 也是原始递归的。证明: 很容易看出 f 的历史函数 F(⃗x, y) 是原始递归的： F(⃗x, 0) = 2g(⃗x)+1; F(⃗x, y + 1) = F(⃗x, y) · p h(⃗x,y,F(⃗x,y))+1 y+1 。所以，f(⃗x, y) = (F(⃗x, y))y 也是原始递归的。引理 ?? 在后面非常有用，尤其是在讨论语法的算术化的时候。第 2 节递归函数 7.2.1 非原始递归函数是不是所有的直观上可计算的函数都是原始递归的呢？答案是否定的。我们可以用“对角线”方法来论证。首先注意：我们直观上有一个程序，它可以系统地把所有原始递归函数枚举出来。比如，我们可以把所有可能的生成序列一一枚举出 6

第7章递归论的基本知识第2节递归函数来。令90,91,表示这样枚举出来的原始递归函数序列。定义函数F:N→N为F(n)= gn(n)+1。这个函数F是直观上可计算的,但它不出现在原始递归函数的序列中,因而不是原始递归的。一个更为具体的例子是所谓的阿克曼函数A(x,y),定义如下: A(0,y)=y+1,A(x+1,0)=A(x,1) A(x+1,y+1)=A(x,A(x+1,y) 例如,A(1,y)=y+2、A(2,y)=2y+3还有A(3,y)=2y+3-3。粗略地说,A(x+1,y) 是通过y次叠代运算A(x,y)而得到的。利用双重归纳,我们不难证明A(x,y)是一个全函数,即,对所有的自然数x和y, A(x,y)都是有定义的。这个归纳的过程同时告诉我们直观上怎样计算阿克曼函数。但它不是原始递归的,原因是它增长得太快了,任何一个原始递归函数最终都会被它优超。具体的断言和证明我们留作习题。 722递归函数从程序语言的角度看,原始递归函数可以处理所有的算术运算、条件判断、以及形如“从i=1到η执行…”这样的循环。我们想一想,同一般的程序语言相比,我们还缺什么呢?答案是,我们还缺少“无(事先给定的)界的循环”,即处理“重复…直到 ”这样的指令。下面的定义试图弥补这一缺陷。定义7.5.令∫:N+1→N为一个全函数。我们称函数g()是从∫通过正则极小化或由正则-算子得到的,如果yf(x,y)=0(称为正则性条件)并且g()是使得f(正,y)=0的最小的yo沿用记号μ,我们把它写成g()=pyf(式,y)=0。定义7.6.全体递归函数的集合为最小的包含所有初始函数,并且对复合,原始递归和正则极小化封闭的函数集合同前一样,如果一个集合的特征函数是一个递归函数,我们则称该集合为一个递归集。递归集就是可判定集合的精确说法定义中的正则性条件Ⅴ过vg(x,y)=0从可计算的角度看是非常复杂的。我们无法能行地判断正则性条件是否成立。很难想象我们在设计一个算法或在写一个程序的时候需要时而不时地检査正则性条件。我们希望能够把它删掉。删掉它的后果是我们对y的搜寻可能永远不停止,因此必须面对所谓的部分函数,即在某些点没有定义的函数。从现在起, 当我们考虑函数∫:A→B时,f的定义域可以是A的一个真子集。对A中的一个点x, 我们用f(x)↓表示“函数f在x点有定义”(或称为“f(x)是收敛的”);而f(x)↑表示函数∫在x点没有定义的”(或称为“f(x)是发散的”)

第 7 章递归论的基本知识第 2 节递归函数来。令 g0, g1, . . . 表示这样枚举出来的原始递归函数序列。定义函数 F : N → N 为 F(n) = gn(n) + 1。这个函数 F 是直观上可计算的，但它不出现在原始递归函数的序列中，因而不是原始递归的。一个更为具体的例子是所谓的阿克曼函数 A(x, y)，定义如下： A(0, y) = y + 1, A(x + 1, 0) = A(x, 1), A(x + 1, y + 1) = A(x, A(x + 1, y))。例如，A(1, y) = y + 2、A(2, y) = 2y + 3 还有 A(3, y) = 2y+3 − 3。粗略地说，A(x + 1, y) 是通过 y 次叠代运算 A(x, y) 而得到的。利用双重归纳，我们不难证明 A(x, y) 是一个全函数，即，对所有的自然数 x 和 y， A(x, y) 都是有定义的。这个归纳的过程同时告诉我们直观上怎样计算阿克曼函数。但它不是原始递归的，原因是它增长得太快了，任何一个原始递归函数最终都会被它优超。具体的断言和证明我们留作习题。 7.2.2 递归函数从程序语言的角度看，原始递归函数可以处理所有的算术运算、条件判断、以及形如“从 i = 1 到 n 执行……”这样的循环。我们想一想，同一般的程序语言相比，我们还缺什么呢？答案是，我们还缺少“无（事先给定的）界的循环”，即处理“重复……直到 ……”这样的指令。下面的定义试图弥补这一缺陷。定义 7.5. 令 f : N n+1 → N 为一个全函数。我们称函数 g(⃗x) 是从 f 通过正则极小化或由正则 µ- 算子得到的，如果 ∀⃗x∃yf(⃗x, y) = 0 （称为正则性条件）并且 g(⃗x) 是使得 f(⃗x, y) = 0 的最小的 y。沿用记号 µ，我们把它写成 g(⃗x) = µy[f(⃗x, y) = 0]。定义 7.6. 全体递归函数的集合为最小的包含所有初始函数，并且对复合，原始递归和正则极小化封闭的函数集合。同前一样，如果一个集合的特征函数是一个递归函数，我们则称该集合为一个递归集。递归集就是可判定集合的精确说法。定义中的正则性条件 ∀⃗x∃yg(⃗x, y) = 0 从可计算的角度看是非常复杂的。我们无法能行地判断正则性条件是否成立。很难想象我们在设计一个算法或在写一个程序的时候需要时而不时地检查正则性条件。我们希望能够把它删掉。删掉它的后果是我们对 y 的搜寻可能永远不停止，因此必须面对所谓的部分函数，即在某些点没有定义的函数。从现在起，当我们考虑函数 f : A → B 时，f 的定义域可以是 A 的一个真子集。对 A 中的一个点 x，我们用 f(x) ↓ 表示“函数 f 在 x 点有定义”（或称为“f(x) 是收敛的”）；而 f(x) ↑ 表示 “函数 f 在 x 点没有定义的”（或称为“f(x) 是发散的”）。 7

第2节递归函数第7章递归论的基本知识 723部分递归函数定义77.令∫为一个部分函数。我们称函数g是从∫通过极小化或由μ-算子得到的,如果 9()=四yⅣz≤y(f(x,2)↓)∧f(x,y)=0。我们解释一下条件Vz≤y(f(x,2)↓)。由于函数f(x,y)可以是部分函数,很有可能在它的最小的根(比如说)出现之前,它在某些点(比如说x)上是没有定义的。这时候我们应该怎样处理呢?让我们参考一下编程时的做法。我们只能耐心地一个点一个点地检验。假如我们跳过a,即使看到了踟这个根,我们也不敢断定它是最小的,因为我们不可能能行地知道∫(x,)是发散的(见后面停机问题的讨论)。因此,我们宁可达不到真正的根,也不能跳过发散点,这就是条件vz≤y(f(z,2)↓)的目的。后面在习题??中, 我们会看到如果允许跳过发散点,则定义出来的函数类比可计算函数类要大。最后再说明点,后面的克林尼正规型定理告诉我们,对部分函数使用极小算子是不那么重要的,每个部分递归函数本质上都可以通过对某个原始递归谓词使用一次极小算子产生出来定义7.8.全体部分递归函数的集合为最小的包含所有初始函数,并且对复合,原始递归和极小化封闭的函数集合。对初学者来说,部分函数的概念可能不容易接受,尤其是我们关心的对象似乎主要是递归(全)函数。后面会提到一些部分函数所具有的一些优点。但我们研究部分函数最重要的原因是由可计算性的本质决定的:每一个算法(或程序)都天然地对应一个部分函数,而不是全函数。在本章中的部分递归函数自然可以是部分函数。但我们使用“递归函数”这个词时, 指的是递归全函数。有时我们为了强调,也会用“递归全函数”。引理711.阿克曼函数是部分递归的全函数我们下面给出证明的梗概。基本思路是搜索一个“包含所有计算所需信息的编码”。这一方面说明极小算子带来的好处,另一方面,确认一个编码包含所有中间步骤的完整信息比确认最终答案要容易,这件事情本身也有意思,后面证明克林尼正规型定理时也会用到这一想法。当然,这也不难理解,确认一个定理的证明是对是错比确认一个猜想是一个定理要容易多了。证明:比照阿克曼函数的定义,我们称一个三元组的有穷集合S为好的,如果它满足下列条件 (a)如果(0,y,2)∈S则z=y+1 (b)如果(x+1,0,2)∈S则(x,1,z)∈S; 8

第 2 节递归函数第 7 章递归论的基本知识 7.2.3 部分递归函数定义 7.7. 令 f 为一个部分函数。我们称函数 g 是从 f 通过极小化或由 µ-算子得到的，如果 g(⃗x) = µy [∀z ≤ y(f(⃗x, z) ↓) ∧ f(⃗x, y) = 0]。我们解释一下条件 ∀z ≤ y(f(⃗x, z) ↓)。由于函数 f(⃗x, y) 可以是部分函数，很有可能在它的最小的根（比如说 y0）出现之前，它在某些点（比如说 z0）上是没有定义的。这时候我们应该怎样处理呢？让我们参考一下编程时的做法。我们只能耐心地一个点一个点地检验。假如我们跳过 z0，即使看到了 y0 这个根，我们也不敢断定它是最小的，因为我们不可能能行地知道 f(⃗x, z0) 是发散的（见后面停机问题的讨论）。因此，我们宁可达不到真正的根，也不能跳过发散点，这就是条件 ∀z ≤ y(f(⃗x, z) ↓) 的目的。后面在习题 ?? 中，我们会看到如果允许跳过发散点，则定义出来的函数类比可计算函数类要大。最后再说明一点，后面的克林尼正规型定理告诉我们，对部分函数使用极小算子是不那么重要的，每个部分递归函数本质上都可以通过对某个原始递归谓词使用一次极小算子产生出来。定义 7.8. 全体部分递归函数的集合为最小的包含所有初始函数，并且对复合，原始递归和极小化封闭的函数集合。对初学者来说，部分函数的概念可能不容易接受，尤其是我们关心的对象似乎主要是递归（全）函数。后面会提到一些部分函数所具有的一些优点。但我们研究部分函数最重要的原因是由可计算性的本质决定的：每一个算法（或程序）都天然地对应一个部分函数，而不是全函数。在本章中的部分递归函数自然可以是部分函数。但我们使用“递归函数”这个词时，指的是递归全函数。有时我们为了强调，也会用“递归全函数”。引理 7.11. 阿克曼函数是部分递归的全函数。我们下面给出证明的梗概。基本思路是搜索一个“包含所有计算所需信息的编码”。这一方面说明极小算子带来的好处，另一方面，确认一个编码包含所有中间步骤的完整信息比确认最终答案要容易，这件事情本身也有意思，后面证明克林尼正规型定理时也会用到这一想法。当然，这也不难理解，确认一个定理的证明是对是错比确认一个猜想是一个定理要容易多了。证明: 比照阿克曼函数的定义，我们称一个三元组的有穷集合 S 为好的，如果它满足下列条件： (a) 如果 (0, y, z) ∈ S 则 z = y + 1； (b) 如果 (x + 1, 0, z) ∈ S 则 (x, 1, z) ∈ S； 8

第 7 章递归论的基本知识第 3 节图灵机 (c) 如果 (x + 1, y + 1, z) ∈ S 则存在一个自然数 u 使得 (x + 1, y, u) ∈ S 且 (x, u, z) ∈ S。注意：一个好的三元组集 S 具有如下性质：如果 (x, y, z) ∈ S，则 (1) z = A(x, y)。 (2) S 包含计算 A(x, y) 过程中所需的所有的“先前的”三元组 (x ′ , y′ , A(x ′ , y′ ))。接下来我们把三元组 (x, y, z) 编码成 ⟨x, y, z⟩ = 2x+13 y+15 z+1；并把一个三元组的编码的有穷集 {u1, · · · , uk} 编码成 ⟨u1, u2, · · · , uk⟩。所以一个三元组的有穷集可以被编码成一个自然数 v。令 Sv 表示编码为 v 的三元组集。则谓词“(x, y, z) ∈ Sv”是原始递归的，因为它等价于“∃i < v((v)i = ⟨x, y, z⟩)”。更进一步，“Sv 是一个好的三元组的集合”也是一个原始递归谓词（练习）。所以谓词 R(x, y, v) := “v 是一个好的三元组集的编码并且 ∃z < v ((x, y, z) ∈ Sv)” 也是原始递归的。于是函数f(x, y) = µvR(x, y, v) 是部分递归的。所以A(x, y) = µz((x, y, z) ∈ Sf(x,y)) 也是部分递归的；并且 f(x, y) 和 A(x, y) 都是全函数。第 3 节图灵机英国数学家图灵是二十世纪最伟大的数理逻辑学家之一，也被人称为计算机科学和人工智能之父。在他 1936 年的文章中 1，他提出了图灵机的概念，并且证明了停机问题是不可判定的，从而解决了希尔伯特提出的判定性问题。虽然哥德尔和丘奇等人也在更早或差不多同时也给出了判定问题的否定答案，但图灵提出的被称为图灵机的计算模型可以被视为纯机械的物理机器，因而比形式系统更能代表任何的机械装置，从而在不可判定问题的解答上更为直观也更有说服力。 7.3.1 图灵机的定义我们先看图灵机的物理描述。图灵分析了一个“计算员（computor）”进行计算的过程，得出了一台图灵机应该包括以下要素： 1On Computable Numbers, with an application to the Entscheidungsproblem, Proc. Lond. Math. Soc. 9

复旦大学：《数理逻辑》课程教学资源（讲义）第7章 递归论基本知识

复旦大学：《数理逻辑》课程教学资源（讲义）第7章递归论基本知识