习题71. (1)证明所有0-元函数都不是原始递归的;但用0-元函数按照(?)定义的函数都是原始 递归的。 (2)证明前驱函数pred(a)是原始递归的,并写出它的一个生成序列。 (3)证明函数f(x)=x是原始递归的 (5)证明二元谓词=和≤都是原始递归的。 (8)假设a^b是某个有穷序列的哥德尔数,我们能断言a和b一定也是哥德尔数吗? (9)任何一个双射∫:Ⅳ→N都可以被视为一种编码,它把一个自然数对(m,n)编为 个自然数k=f(m,n)。它的逆函数在两个分量上的(分别)投影f1和f2可视为对 它的解码,即从f(k)=m和2(k)=n,其中k=f(m,n)。找出一个原始递归的编 码函数∫:Ⅳ2→Ⅳ使得它的两个解码函数f1和f2也是原始递归的。 (10)回忆一下:菲波那契序列的定义如下:f(0)=f(1)=1且对任何n∈N,f(n+2) f(n)+f(n+1)。证明菲波那契序列是原始递归的。[这显然是强递归定理的一个特 例。建议大家模仿强递归定理的证明方式,而不是直接引用强递归定理。 习题72 (1)证明阿克曼函数A(x,y)是一个全函数。 (2)证明对任何一个原始递归函数f()都存在一个r∈N使得对所有的,f()< A(r,max{})。由此证明阿克曼函数不是原始递归的。 习题73 (1)分别编写计算零函数,后继函数和投射函数mn的图灵机程序 (2)编写一个判定“x是否等于y”的图灵机程序,即,给定输入x和y,该程序输 出1如果x=y;否则输出0。[这道题请大家写出具体的四元组
习题 7.1. (1) 证明所有 0-元函数都不是原始递归的；但用 0-元函数按照 (??) 定义的函数都是原始 递归的。 (2) 证明前驱函数 pred(x) 是原始递归的，并写出它的一个生成序列。 (3) 证明函数 f(x) = x x 是原始递归的。 (5) 证明二元谓词 = 和 ≤ 都是原始递归的。 (8) 假设 a^b 是某个有穷序列的哥德尔数，我们能断言 a 和 b 一定也是哥德尔数吗？ (9) 任何一个双射 f : N 2 → N 都可以被视为一种编码，它把一个自然数对 (m, n) 编为一 个自然数 k = f(m, n)。它的逆函数在两个分量上的（分别）投影 f1 和 f2 可视为对 它的解码，即从 f1(k) = m 和 f2(k) = n，其中 k = f(m, n)。找出一个原始递归的编 码函数 f : N 2 → N 使得它的两个解码函数 f1 和 f2 也是原始递归的。 (10) 回忆一下：菲波那契序列的定义如下：f(0) = f(1) = 1 且对任何 n ∈ N，f(n + 2) = f(n) + f(n + 1)。证明菲波那契序列是原始递归的。[这显然是强递归定理的一个特 例。建议大家模仿强递归定理的证明方式，而不是直接引用强递归定理。] 习题 7.2. (1) 证明阿克曼函数 A(x, y) 是一个全函数。 (2) 证明对任何一个原始递归函数 f(⃗x) 都存在一个 r ∈ N 使得对所有的 ⃗x，f(⃗x) < A(r, max{⃗x})。由此证明阿克曼函数不是原始递归的。 习题 7.3. (1) 分别编写计算零函数，后继函数和投射函数 π n i 的图灵机程序。 (2) 编写一个判定“x 是否等于 y”的图灵机程序，即，给定输入 x 和 y，该程序输 出 1 如果 x = y；否则输出 0。[这道题请大家写出具体的四元组。] 1
(3)证明:如果一个函数f(x)可以被一台字母表为{0,1,a}的图灵机M1计算,则它也 可以被一台字母表为(0,1}的图灵机M2计算。[不难看出,对有穷的字母表也有类 似的结论。注意,我们并没有断言M可以在任何格局上模拟M1。] (4)图灵机的转换函数也可以用形如qaqL,qaqR的五元组来表示。证明用五元组表 示的图灵机等价于某台用四元组表示的图灵机,反之亦然。[习题中未加定义的概念 请大家自行补上。] (5)用有向转移图的方式写一个图灵程序计算乘法f(x,y)=x·yc 习题7.4 (1)(给出)证明(的梗概):图灵可计算函数构成的类对原始递归和极小算子都是封闭 的。 (2)证明函数IN,NEXT,OUT都是原始递归的。 (3)证明定理??。 习题7.5 (3)证明如下形式的分情形定义定理:如果A是一个递归可枚举集且∫为一个部分递归 函数,则函数 9()-=a),如果∈A ↑,否则。 是部分递归的。并举例说明,函数 h(.) f(x),如果x∈A; 否则。 不一定是部分递归的。 (4)证明存在一个部分递归函数v(x,y)使得函数g(x):=最小的满足v(x,y)=0的y不 是部分递归的。这说明在定义极小算子时,条件vz≤叭(∫(云;z)↓)是必要的。提 考虑函数 0,如果y=1或者(y=0且y(x)↓) ↑,否则
(3) 证明：如果一个函数 f(x) 可以被一台字母表为 {0, 1, a} 的图灵机 M1 计算，则它也 可以被一台字母表为 {0, 1} 的图灵机 M2 计算。[不难看出，对有穷的字母表也有类 似的结论。注意，我们并没有断言 M2 可以在任何格局上模拟 M1。] (4) 图灵机的转换函数也可以用形如 qaa′ q ′L, qaa′ q ′R 的五元组来表示。证明用五元组表 示的图灵机等价于某台用四元组表示的图灵机，反之亦然。[习题中未加定义的概念 请大家自行补上。] (5) 用有向转移图的方式写一个图灵程序计算乘法 f(x, y) = x · y。 习题 7.4. (1) （给出）证明（的梗概）：图灵可计算函数构成的类对原始递归和极小算子都是封闭 的。 (2) 证明函数 IN, NEXT, OUT 都是原始递归的。 (3) 证明定理 ??。 习题 7.5. (3) 证明如下形式的分情形定义定理：如果 A 是一个递归可枚举集且 f 为一个部分递归 函数，则函数 g(x) = { f(x), 如果 x ∈ A； ↑, 否则。 是部分递归的。并举例说明，函数 h(x) = { f(x), 如果 x ∈ A； 0, 否则。 不一定是部分递归的。 (4) 证明存在一个部分递归函数 ψ(x, y) 使得函数 g(x) := 最小的满足 ψ(x, y) = 0 的 y 不 是部分递归的。这说明在定义极小算子时，条件 ∀z ≤ y(f(⃗x; z) ↓) 是必要的。提示： 考虑函数 ψ(x, y) = { 0, 如果 y = 1 或者（y = 0 且 φx(x) ↓）； ↑, 否则。 2
(5)证明:如果h:N→N是一个部分递归函数且AcN是一个递归可枚举集,则A的 原像集h-4]和限制在A上的值域h[4都是递归可枚举的。还有,如果A和h都 是递归的,则h-[4]也是递归的;h[4]一定递归吗? (6)证明集合Ko={(x,y)∈N2:φ(y)↓}不是递归的。[这是停机问题的一般形式。]
(5) 证明：如果 h : N → N 是一个部分递归函数且 A ⊆ N 是一个递归可枚举集，则 A 的 原像集 h −1 [A] 和 限制在 A 上的值域 h[A] 都是递归可枚举的。还有，如果 A 和 h 都 是递归的，则 h −1 [A] 也是递归的；h[A] 一定递归吗？ (6) 证明集合 K0 = {(x, y) ∈ N 2 : φx(y) ↓} 不是递归的。[这是停机问题 的一般形式。] 3
