计算理论导引急救包

1、计算理论导引期末试卷南京大学计算机科学与技术系2014 年 6 月本试卷满分 100 分，共五题。时间 2 小时。一. （20 分） 解释下列概念:一般递归函数数论全函数的 可定义性演算的不动点定理Turing 机（Turing Machine）停机问题1学号成绩二. （20 分） 设 A 表示 EF, B 表示 PRF EF, C 表示 GRF PRF, D 表示RF GRF，E 表示不可计算的数论函数类。判定下列数论函数所属的函数类，选择 A、B、C、D、E 之一，填在题后的表格中。(1)(2)f : N N 为处处无定义的函数；f : N N 定义为若 n 为平方数否则0,无定义,f (

2、n) =(3)(4)Ackermann 函数；f : N2 N 定义为n若 n m = 0C ,mf (n, m) =无定义, 否则这里 Cn 表示从 m 个不同元素中取出 n 个元素的所有组合的个数；mf : N N 定义为 f (n) = 10n ，这里 x 为对 x 向下取整， 为圆周(5)率；(6)f : N N 定义为1, 若存在 M 使得 n = M 且 M 有 -nff (n) =2, 否则.(n+1) f : N N 定义为 f (n) = 23n 层；(7)(8)f : N N 定义为0, 若存在 Turing 机 M 使 n = M 且 M 对于一切输入皆停机1, 否则f

3、(n) =Gdel 的 函数；.nm f : N2 N 定义为 f (n, m) = nnn 个 n。(9)(10)对于上述各函数，判定其所属函数类，选择 A、B、C、D、E 之一，填在下面的表格中。2(1)(2)(3)(4)(5)(6)(7)(8)(9)(10)三. （20 分） 在 演算中，判断下列表述是否正确。若正确，则在题后的表格中对应的位置打，否则打。(1)(2)(3)(4)(5)(6)(7)(8)M = N M x := L = N x := L；x. (z. yz)x) = z. yz；x. (xx) = x. ()；KSSS 有 -nf SS； K = S；(x. y)(x.

4、xx)(x. xx) 无 -nf；x(x) x，这里 为 Turing 定义的不动点组合子；设 D U , U，则 D = U2，这里 n 为自然数 n 的 Church 数329312项；2 3 = 9 ，这里 n(9)(10)为自然数 n 的Church 数项；若 M = N ，则存在 T 使 M T 且 N T 。对于上述各等式，判定其是否正确。若正确，则在下面表格中对应的位置打，否则打。3(1)(2)(3)(4)(5)(6)(7)(8)(9)(10)四. （20 分） 分别构造计算下列函数的Turing 机：(1) f (x) = 2x；(2) f (x) = x2； x(3) f (

5、x) =；21(4) f (x) = x。24五. （20 分）(1)What is the Church-Turings thesis?何谓Church-Turing 论题？(2)Let f (n) be the n-th digithe decimal expanof the real number cos(1), ewhere cos(x) is the cosine function. For example, supt cos(1) = 0.a1a2a3 ,wee f (0) = 0, f (1) = a1, f (2) = a2, . Prove by Church-Turings thesist the function f is computable.令 f (n) 为实数 cos(1) 的十进制展开式中的第 n 位数字，其中 cos(x) 是余弦函数。例如，假设 cos(1) = 0.a1a2a3 ，则有 f (0) = 0，f (1) = a1，f (2) = a2， 。利用 Ch