第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