经典计算计算模型计算机科学导论

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 递 归 函 数 可计算函数(直观讨论) 1. f(n) = n2//小学生都会计算 2. q(n) = ? ?// 计算12, 22, 32, …, 并与n比较, // 若k2?n ? (k+1)2>n, 结果为k 3. p(n) = 第n个素数// 逐个检查1, 2, 3, …是否为素 // 数, 直至找到第n个素数 (上述计算不仅包括加减乘除，还有比较等) 1 若在?的十进制表示中有连续x个5 4. g(n) = 0 其他情况完全无法计算 n 递 归 函 数 可计算函数(直观讨论) 分析计算过程，找出最简单的计算 开方：转化为平方、两数的比较、取“最后一个”例： q(n) = ? ? n 递 归 函 数 可计算函数(直观讨论) 分析计算过程，找出最简单的计算 开方：转化为平方、两数的比较、取“最后一个” 除法：转化为乘法，a/b可通过计算b?1, b?2, …, 并同a比较 例：在函数“p(n) = 第n个素数”的计算中用到 递 归 函 数 可计算函数(直观讨论) 分析计算过程，找出最简单的计算 开方：转化为平方、两数的比较、取“最后一个” 除法：转化为乘法，a/b可通过计算b?1, b?2, …, 并同a比较 乘法：转化为加法 加法：转化为加1运算 一般的计算过程究竟能转化为哪些最基本计算的 计算过程？ 原始递归函数 基本函数(也称初始函数)集合? 后继函数：s(x) = x +1 零函数：o(x) = 0 射影函数Pj (n)(x1, x2, …, xn) = xj (1? j ? n) 基本运算集合? 代入运算：f (x1, x2, …, xn) = h(g1(x1, x2,…, xn), g2(x1, x2,…, xn),…, gm(x1, x2,…, xn)) 当m, n = 1并且略去下角标，就是 f (x) = h(g(x)) 原始递归函数 基本函数(也称初始函数)集合? 后继函数：s(x) = x +1 零函数：o(x) = 0 射影函数Pj (n)(x1, x2, …, xn) = xj (1? j ? n) 基本运算集合? 代入运算：f (x1, x2, …, xn) = h(g1(x1, x2,…, xn), g2(x1, x2,…, xn),…, gm(x1, x2,…, xn)) 原始递归运算： f (x1, …, xn?1, 0) = g(x1, …, xn?1) f(x1, …, xn?1, xn+1) = h(x1, …, xn?1, xn, f(x1, …, xn)) 原始递归函数 基本函数(也称初始函数)集合? 后继函数：s(x) = x +1 零函数：o(x) = 0 射影函数Pj (n)(x1, x2, …, xn) = xj (1? j ? n) 基本运算集合? 代入运算：f (x1, x2, …, xn) = h(g1(x1, x2,…, xn), g2(x1, x2,…, xn),…, gm(x1, x2,…, xn)) 原始递归运算，当n = 1并略去下角标，就是 f (0) = c f(x+1) = h(x, f(x)) 原始递归函数 基本函数(也称初始函数)集合? 后继函数：s(x) = x +1 零函数：o(x) = 0 射影函数Pj (n)(x1, x2, …, xn) = xj (1? j ? n) 基本运算集合? 代入运算：f (x1, x2, …, xn) = h(g1(x1, x2,…, xn), g2(x1, x2,…, xn),…, gm(x1, x2,…, xn)) 原始递归运算： f (x1, …, xn?1, 0) = g(x1, …, xn?1) f(x1, …, xn?1, xn+1) = h(x1, …, xn?1, xn, f(x1, …, xn)) 原始递归函数 原始递归函数的定义 由?中的函数通过有限次?中的运算得到的函数 叫做原始递归函数 直观来看，原始递归函数显然是可以计算的 ?中的基本函数非常简单，经过运算后仍然是处处定义的 原始递归函数类还是相当广泛的 下面举例说明自然数上的一些函数属于原始递归函数类 原始递归函数 例1 1. ak