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