第7章递归论的基本知识 递归论是递归函数论的简称。它数理逻辑的一个重要分支,由于递归函数是直观上的 可计算函数的精确化,递归论也被称为可计算性理论。 递归论创立于1930年代,最初是为了精确定义可计算性(即可判定性),有了可计 算性(可判定性)的精确定义,人们才可以证明什么是不可计算的或不可判定的。很多 经典的不可判定性结果,如停机问题和一阶逻辑的普遍有效性都是不可判定的,都是在 1930年代建立的。之后人们的注意力转向了各种相对可计算性和由此产生的(不可解) 度的研究。递归论的现代口号是研究可定义性,因为可定义性是可计算性的一种自然推 。依照对可定义性要求苛刻程度的大小,递归论的研究范围包括:(部分)理论计算机 科学,古典递归论(一阶算术),(部分)描述集合论和(部分)集合论。还有各类高等递 归论等等。 我们介绍递归论的动机除了了解可计算性概念之外,在系统内“表示”递归关系也是 证明哥德尔不完全性定理的重要组成部分。 第1节原始递归函数 711原始递归函数的定义 定义71.以下三类函数称为初始函数:零函数Z(x)=0,后继函数S(x),和投射函数 r(x1,…,xn)=x1,其中n为正整数且1≤i≤n 令n为自然数,且g:Nn→N和h:Nn+2→N分别为m-元和(n+2)-元函数。我们 称(n+1)-元函数∫:N+1→N为从g和h经原始递归得到的,如果 f(rr 且 rn,y+1)=h(x1,……,xn,y,f(x1 )) (注意:这里的y+1实际上是y的后继S(y),严格地说,并不是加法。) 为方便起见,我们规定一个0-元函数g就是一个固定常数c,这样一元函数∫也可以 像上面一样从g和h经原始递归得到 f(0)=c,且f(y+1)=h(y,f(y) (7.1)
第 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章递归论的基本知识 定义72.全体原始递归函数的集合C是最小的满足下列条件的集合 1)所有的初始函数都在C中。 (2)C对函数复合封闭,即,如果f(x1,…,xn)=g(h1(x1,…,xn),…,hr(x1,…,xrn), 并且g(v,…,y)和ha(x1,…,xn)(1≤i≤r)都在C中,则∫也在C中。 (3)C对原始递归封闭。 我们称C中的元素为原始递归函数。 在第??章第??节中我们讨论过关于闭包的“自上而下”和“自下而上”的定义方 式,并且论证了它们是等价的。定义??是“自上而下”的,换成“自下而上”的等价 形式,我们有:每个原始递归函数f都有一个有穷的生成序列:《f1,f2,…,f),其中 fn=f并且对任意1≤i≤n,f或者是初始函数,或者是由前面的函数通过复合或 原始递归得到的。注意生成序列是不唯一的。我们可以沿着生成序列做归纳。例如,我 们可以证明所有的原始递归函数都是全函数,即,如果∫:Ⅳ→N是原始递归的,则 dom∫=Ⅳ(练习)。此外,也请大家思考一下所有的原始递归函数的确都是直观上可计 算的 例71.自然数的加法是原始递归的。通常是利用后继函数由下列递归方程定义的 (y+1)=S(x+y) 作为例子,我们给出它的一个生成序列:(今后我们将只给递归方程,而将生成序列 留给对方程有疑义的读者。) S(x1)(后继函数),H(x1)=x1(一元投射函数),n3(x1,x2,x3)=x3(三元投射函 数),g(x1,x2,x3)=Soπ3(x1,x2,x3)=S(x3)(第一项与第三项的复合),f(x1,x2)(由 第二项和第四项经原始递归得到) ∫(x1,y+1)=g(x1,y,f(x1,y) 显然,f(x,y)=x+ 引理7.1.下列函数都是原始递归的: 1.常数函数C(x1,…,xn)=k,其中k是一个固定的自然数。 2乘法函数x·y、指数函数xy和阶乘函数x!
第 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节原始递归函数 3.如下定义的非零检测函数σ和零检测函数δ 0,如果x=0; 1,如果x=0; 如果x≠ 6(x) 0,如果x≠ 4.前驱函数pred(x) 5.如下定义的截断减法(或减法) 如果 否则 证明:练习 利用投射函数,我们可以将一个原始递归函数的自变量任意重排,所得到的仍是原始 递归函数。具体地说,我们有下面的引理 引理72令f:Ⅳ→N为一个原始递归函数。定义一个新的函数g:N→N为g(x1,…,xr)= f(,…,纵),其中每个v或者是x1(1≤i≤r)或者是一个常数。则g也是原始递归 的 证明:g可以通过复合从f和投影或常数函数得到。 例如,如果f(x,y)是原始递归的,则g(x)=f(x,x)和h(x,y,z)=f(z,y)也是。 71,2原始递归集合和谓词 在数学中,人们常常利用特征函数把集合“转化”成函数。对一个k-元谓词P,我 们也可以定义它的特征函数为 1,如果P()成立; XP(C) 0,否则 利用特征函数,我们很自然地把原始递归的概念从函数扩展到集合和谓词。 我们称Ⅳ的一个子集A或一个k-元谓词P为原始递归的,如果它的特征函数是 个原始递归函数。一个k-元谓词P为原始递归的也可等价地定义为集合{:P(动}是一 个原始递归的集合。 例如,二元谓词=和≤都是原始递归的(练习)。 引理73. 1.如果A,B≤Ⅳ都是原始递归的集合,则Ⅳ-A,AUB和A∩B也是
第 7 章 递归论的基本知识 第 1 节 原始递归函数 3. 如下定义的非零检测 函数 σ 和零检测 函数 δ: σ(x) = { 0, 如果 x = 0； 1, 如果 x ̸= 0。 δ(x) = { 1, 如果 x = 0； 0, 如果 x ̸= 0。 4. 前驱函数 pred(x)。 5. 如下定义的截断减法 （或减法） x−˙ y = { 0, 如果 x < y； x − y, 否则。 证明: 练习。 利用投射函数，我们可以将一个原始递归函数的自变量任意重排，所得到的仍是原始 递归函数。具体地说，我们有下面的引理： 引理7.2. 令 f : N k → N 为一个原始递归函数。定义一个新的函数g : N r → N 为 g(x1, · · · , xr) = f(y1, · · · , yk)，其中每个 yj 或者是 xi（1 ≤ i ≤ r）或者是一个常数。则 g 也是原始递归 的。 证明: g 可以通过复合从 f 和投影或常数函数得到。 例如，如果 f(x, y) 是原始递归的，则 g(x) = f(x, x) 和 h(x, y, z) = f(z, y) 也是。 7.1.2 原始递归集合和谓词 在数学中，人们常常利用特征函数把集合“转化”成函数。对一个 k-元谓词 P ，我 们也可以定义它的特征函数为： χP (⃗x) = { 1, 如果 P(⃗x) 成立; 0, 否则。 利用特征函数，我们很自然地把原始递归的概念从函数扩展到集合和谓词。 我们称 N k 的一个子集 A 或一个 k-元谓词 P 为原始递归的，如果它的特征函数是一 个原始递归函数。一个 k-元谓词 P 为原始递归的也可等价地定义为集合 {⃗x : P(⃗x)} 是一 个原始递归的集合。 例如，二元谓词 = 和 ≤ 都是原始递归的（练习）。 引理 7.3. 1. 如果 A, B ⊆ N k 都是原始递归的集合，则 N k − A, A ∪ B 和 A ∩ B 也是。 3
第1节原始递归函数 第7章递归论的基本知识 2.如果P和Q都是原始递归的谓词,则→P,PVQ和P∧Q也是。 引理74(分情形定义)如果∫和彡都是原始递归函数,并且P是原始递归谓词,则函数 f(r f1(x),如果P(x)成立 f2(x),否则 也是原始递归的。 用程序语言来说,我们可以执行条件判断的指令。 证明:∫(x)=f(x)XP(x)+f2(x)(1-xP(x) 现在我们可以处理四则运算的最后一则运算-除法了。首先用符号quo(x,y)和rem(x,y)分 别表示用x去除y而得到的商和余数。为了使它们成为全函数,我们规定quo(0,y) 0和rem(0,y) 引理75.函数quo(x,y)和rem(x,y)都是原始递归的。 证明:基本思路是利用下面的递归定义,我们把对定义的仔细分析留给读者。 rem(a,y+1)= em(x,y)+1,如果rem(x,y)+1≠x 否则。 和 quo(a, y+ 1) quo(x,y)+1,如果rem(x,y)+1=x (x,y),否则 回忆一下关于有界量词的定义。我们定义(丑x<a)yp(x)为彐(x<a∧y(x)和定 义(x<a)y(x)为r(x<a→y(x)。 接下来我们引进有界极小算子。下文中的希腊字母p可以读作“最小的” 定义73.令P(,2)为一个(k+1)-元的性质。定义 (1z≤y)P(x,z) 最小的满足P(,z)且≤y的z,如果它存在; y+1 否则 引理76.如果f(,y)是原始递归的,则有界和∑<:f(x,y)和有界积Ⅱl<:f(x,y)都是 原始递归的。 证明:练习
第 1 节 原始递归函数 第 7 章 递归论的基本知识 2. 如果 P 和 Q 都是原始递归的谓词，则 ¬P，P ∨ Q 和 P ∧ Q 也是。 引理 7.4 (分情形定义). 如果 f1 和 f2 都是原始递归函数，并且 P 是原始递归谓词，则函数 f(x) = { f1(x), 如果 P(x) 成立； f2(x), 否则 也是原始递归的。 用程序语言来说，我们可以执行条件判断的指令。 证明: f(x) = f1(x)χP (x) + f2(x)(1−˙ χP (x))。 现在我们可以处理四则运算的最后一则运算—除法了。首先用符号quo(x, y) 和 rem(x, y) 分 别表示用 x 去除 y 而得到的商和余数。为了使它们成为全函数，我们规定 quo(0, y) = 0 和 rem(0, y) = 0。 引理 7.5. 函数 quo(x, y) 和 rem(x, y) 都是原始递归的。 证明: 基本思路是利用下面的递归定义，我们把对定义的仔细分析留给读者。 rem(x, y + 1) = { rem(x, y) + 1, 如果 rem(x, y) + 1 ̸= x； 0, 否则。 和 quo(x, y + 1) = { quo(x, y) + 1, 如果 rem(x, y) + 1 = x； quo(x, y), 否则。 回忆一下关于有界量词 的定义。我们定义 (∃x < a)φ(x) 为 ∃x(x < a ∧ φ(x)) 和定 义 (∀x < a)φ(x) 为 ∀x(x < a → φ(x))。 接下来我们引进有界极小算子。下文中的希腊字母 µ 可以读作“最小的”。 定义 7.3. 令 P(⃗x, z) 为一个 (k + 1)-元的性质。定义 (µz ≤ y)P(⃗x, z) = { 最小的满足 P(⃗x, z) 且 ≤ y 的 z, 如果它存在； y + 1, 否则。 引理 7.6. 如果 f(⃗x, y) 是原始递归的，则有界和 ∑ y≤z f(⃗x, y) 和有界积 ∏ y≤z f(⃗x, y) 都是 原始递归的。 证明: 练习。 4
第7章递归论的基本知识 第1节原始递归函数 我们用符号X:=Y表示X是按照Y来定义的,或按照Y定义的那个X。 引理77.假定P(x,x)是一个原始递归的谓词。则 )谓词E(,y):=(3z≤y)P(x,z)和A(,y):=(z≤)P(正,z)都是原始递归的。 b)函数f(x,y):=(z≤y)P(z,z)也是原始递归的 证明:(a)根据定义,我们有:谓词(vz≤y)P(,2)为真当且仅当∏syxP(,2)=1;并 且谓词(彐z≤y)P(x,z)等价于一(Vz≤y)-P(z,z)。由此可以得到(a)。 今()只须注意(2≤y)P(,2)=∑=0I=0x(n)即可。特别注意当满足条件 不存在时,等式右边恰恰等于y+1。 713编码 我们下面讨论一些有关素数的可计算性,目的是利用素数分解定理来编码 引理7.8.(1丿)谓词“x整除y”是原始递归的。 2)谓词“x是合数”和“x是素数”都是原始递归的 (3)函数p(n):=第n个素数是原始递归的。这个函数我们今后经常会用到。p(m)也常 被写作pn,例如,p=2,p1=3,P2=5,…等等。 证明:练习。 我们现在可以利用素数分解定理来能行地编码了。 定义74.(以)我们用尖括号(aon…,an)来表示乘积p+ 并把它称为有穷 序列(ao,…,an)的哥德尔数。定义空序列()的哥德尔数为1 (2)定义函数h:N→N为lh(a)=k≤a(Pk十a)。我们称lha)为长度函数,因 为h(1)=0且对于任意的哥德尔数a={a0,…,an},都有lha)=n+1 (3)定义关于a和i的二元函数(a)1=k≤a四+2+d。我们称(a)为分量函数,因为 它刚好从编码为a的有穷序列中挑出第i项:对任意的哥德尔数a={(a,…,an}), (a)=a1(0≤i≤n)。 4)对自然数a,b定义串接函数a^b如下 i<Ih(b
第 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