計(jì)算理論導(dǎo)引急救包

1、計(jì)算理論導(dǎo)引期末試卷南京大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系2014 年 6 月本試卷滿(mǎn)分 100 分，共五題。時(shí)間 2 小時(shí)。一. （20 分） 解釋下列概念:一般遞歸函數(shù)數(shù)論全函數(shù)的 可定義性演算的不動(dòng)點(diǎn)定理Turing 機(jī)（Turing Machine）停機(jī)問(wèn)題1學(xué)號(hào)成績(jī)二. （20 分） 設(shè) A 表示 EF, B 表示 PRF EF, C 表示 GRF PRF, D 表示RF GRF，E 表示不可計(jì)算的數(shù)論函數(shù)類(lèi)。判定下列數(shù)論函數(shù)所屬的函數(shù)類(lèi)，選擇 A、B、C、D、E 之一，填在題后的表格中。(1)(2)f : N N 為處處無(wú)定義的函數(shù)；f : N N 定義為若 n 為平方數(shù)否則0,無(wú)定義,f (

2、n) =(3)(4)Ackermann 函數(shù)；f : N2 N 定義為n若 n m = 0C ,mf (n, m) =無(wú)定義, 否則這里 Cn 表示從 m 個(gè)不同元素中取出 n 個(gè)元素的所有組合的個(gè)數(shù)；mf : N N 定義為 f (n) = 10n ，這里 x 為對(duì) 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 機(jī) M 使 n = M 且 M 對(duì)于一切輸入皆停機(jī)1, 否則f

3、(n) =Gdel 的 函數(shù)；.nm f : N2 N 定義為 f (n, m) = nnn 個(gè) n。(9)(10)對(duì)于上述各函數(shù)，判定其所屬函數(shù)類(lèi)，選擇 A、B、C、D、E 之一，填在下面的表格中。2(1)(2)(3)(4)(5)(6)(7)(8)(9)(10)三. （20 分） 在 演算中，判斷下列表述是否正確。若正確，則在題后的表格中對(duì)應(yīng)的位置打，否則打。(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) 無(wú) -nf；x(x) x，這里 為 Turing 定義的不動(dòng)點(diǎn)組合子；設(shè) D U , U，則 D = U2，這里 n 為自然數(shù) n 的 Church 數(shù)329312項(xiàng)；2 3 = 9 ，這里 n(9)(10)為自然數(shù) n 的Church 數(shù)項(xiàng)；若 M = N ，則存在 T 使 M T 且 N T 。對(duì)于上述各等式，判定其是否正確。若正確，則在下面表格中對(duì)應(yīng)的位置打，否則打。3(1)(2)(3)(4)(5)(6)(7)(8)(9)(10)四. （20 分） 分別構(gòu)造計(jì)算下列函數(shù)的Turing 機(jī)：(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) 為實(shí)數(shù) cos(1) 的十進(jìn)制展開(kāi)式中的第 n 位數(shù)字，其中 cos(x) 是余弦函數(shù)。例如，假設(shè) cos(1) = 0.a1a2a3 ，則有 f (0) = 0，f (1) = a1，f (2) = a2， 。利用 Ch