計算理論導引急救包

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