《经典计算的计算模型计算机科学导论第五讲.ppt》由会员分享，可在线阅读，更多相关《经典计算的计算模型计算机科学导论第五讲.ppt（47页珍藏版）》请在三一文库上搜索。
1、经典计算的计算模型 计算机科学导论第五讲,计算机科学技术学院 陈意云 0551-63607043 ,课 程 内 容,课程内容 围绕学科理论体系中的模型理论, 程序理论和计算理论 1. 模型理论关心的问题 给定模型M，哪些问题可以由模型M解决；如何比较模型的表达能力 2. 程序理论关心的问题 给定模型M，如何用模型M解决问题 包括程序设计范型、程序设计语言、程序设计、形式语义、类型论、程序验证、程序分析等 3. 计算理论关心的问题 给定模型M和一类问题, 解决该类问题需多少资源,讲 座 提 纲,基本知识 计算、计算模型、并行计算模型 图灵机概述 图灵的基本思想、基本图灵机、图灵机的变种 演算 表
2、达式的文法、 演算的变换规则、Church数码 递归函数 直观意义的可计算函数、原始递归函数、递归函数,基 本 知 识,计算 抽象地说，计算就是从一个符号序列 得出另一个符号序列（从 出发，在有限步内真正求出） : 12+3, : 15 /该计算是加法 : x x, : 2x /该计算是微分 : 英文句子, : 含意相同的中文句子 /翻译 : 一组公理和推理规则, : 一个定理 /定理证明 下面的f是完全定义的函数，但函数值求不出来 1 若在 的十进制表示中有连续x个5 f(x) = 0 其他情况,基 本 知 识,计算 不要狭隘理解计算 很多非数值问题（如文字识别，图像处理等）都 可以通过转化
3、成为数值问题来交给计算机处理（可 以在有限步骤内被解决） 不要对计算有过高预期 哥德巴赫猜想问题不属于“可计算问题”之列， 因为计算机无法给出数学意义上的证明 没有任何理由期待计算机能解决世界上所有的问 题,基 本 知 识,计算模型 刻画计算概念的抽象形式系统或数学系统 如图灵机、演算、递归函数和Post系统 在可计算性理论和计算复杂性理论中，计算模型 是指包括一组操作及其代价的抽象机器 可用来实现算法 可度量算法的执行时间和空间的复杂性 可分析算法需要的计算资源 可讨论算法或计算机的局限,基 本 知 识,并行计算模型 通常指把各种（至少一类）并行计算机的基本特 征抽象出来，形成的抽象并行机器
4、 对于串行计算机，全世界基本上都在使用冯诺伊 曼的计算模型；对于并行计算，一些有价值的参考 计算模型已提出，但没有一个能被大家接受的统一 的计算模型 新型计算的计算模型 网域计算模型、云计算模型、海计算模型,图 灵 机 概 述,图灵的基本思想 用机器来模拟人用纸和笔进行数学计算的过程， 该过程由两类简单动作的序列构成 在纸上写出或擦除某个符号 把注意力从纸上一个位置移到另一个位置 决定下一步动作的依据：纸上某个位置的符号和 人当前的思维状态 为模拟人的这种计算过程，图灵在20世纪30年代 构造了一种假想的简单机器,图 灵 机 概 述,基本图灵机 T= Q, , b, , q0, F, Q: 有
5、穷非空的状态集 : 有穷非空的带符号集 b: 空白符号 b: 输入符号集 q0Q: 开始状态 FQ: 终止状态集 :(QF ) Q L, R: 迁移函数， L和R表 示读写头的左右移 例如： (q0, 0)(q1, X, R), (q1, 1)(q2, Y, L),图 灵 机 概 述,例： 识别语言 L=0n1n | n 1 的图灵机 策略：从左向右轮 番把带上最左的0和1分别写成X和Y（期间要向右和 向左移动读写头），直至全部写完 T= Q, , b, , q0, F, Q = q0, q1, , q5 = 0, 1, b, X, Y = 0, 1 F = q5 见下一页,图 灵 机 概 述
6、,例： 识别语言 L=0n1n | n 1 的图灵机 (q0, 0)(q1, X, R) (q2, 0)(q4, 0, L) (q1, 0)(q1, 0, R) (q4, 0)(q4, 0, L) (q1, Y)(q1, Y, R) (q4, X)(q0, X, R) (q1, 1)(q2, Y, L) (q3, Y)(q3, Y, R) (q2, Y)(q2, Y, L) (q3, B)(q5, Y, R) (q2, X)(q3, X, R),图 灵 机 概 述,例： 识别语言 L=0n1n | n 1 的图灵机 识别000111的动作 (q0, 0)(q1, X, R),图 灵 机 概 述
7、,例： 识别语言 L=0n1n | n 1 的图灵机 识别000111的动作 (q0, 0)(q1, X, R) (q1, 0)(q1, 0, R),图 灵 机 概 述,例： 识别语言 L=0n1n | n 1 的图灵机 识别000111的动作 (q0, 0)(q1, X, R) (q1, 0)(q1, 0, R) (q1, 0)(q1, 0, R),图 灵 机 概 述,例： 识别语言 L=0n1n | n 1 的图灵机 识别000111的动作 (q0, 0)(q1, X, R) (q1, 0)(q1, 0, R) (q1, 0)(q1, 0, R) (q1, 1)(q2, Y, L),图 灵
8、 机 概 述,例： 识别语言 L=0n1n | n 1 的图灵机 识别000111的动作 (q0, 0)(q1, X, R) (q1, 0)(q1, 0, R) (q1, 0)(q1, 0, R) (q1, 1)(q2, Y, L) (q2, 0)(q4, 0, L),图 灵 机 概 述,例： 识别语言 L=0n1n | n 1 的图灵机 识别000111的动作 (q0, 0)(q1, X, R) (q1, 0)(q1, 0, R) (q1, 0)(q1, 0, R) (q1, 1)(q2, Y, L) (q2, 0)(q4, 0, L) (q4, 0)(q4, 0, L),图 灵 机 概 述
9、,例： 识别语言 L=0n1n | n 1 的图灵机 识别000111的动作 (q0, 0)(q1, X, R) (q1, 0)(q1, 0, R) (q1, 0)(q1, 0, R) (q1, 1)(q2, Y, L) (q2, 0)(q4, 0, L) (q4, 0)(q4, 0, L) (q4, X)(q0, X, R),然后又从q0 继续,图 灵 机 概 述,图灵机的变种 纸带两端都可以无限伸展 多道图灵机 多带图灵机 不确定图灵机，等等 它们的计算能力都等价于基本图灵机 图灵机的计算能力 等价于下面讨论演算和递归函数, 演 算,演算的历史 Church在20世纪30年代研究的定义可计
10、算函数的一种形式体系 Kleene在1936年证明，可定义的所有自然数函数正好是所有的递归函数 Turing在1937年证明，可定义的数值函数正好是Turing机可计算的函数 起初演算是无类型的，因在基于无类型演算的逻辑中发现一个悖论，导致类型化演算的研究 演算一直影响着程序设计语言的研究, 演 算,演算和程序设计语言 20世纪50年代，无类型演算明显影响了Lisp语言的研究 20世纪60年代认识到，程序设计语言的语义可以通过使用拓展的演算给出 现代的观点认为，类型化演算引导对程序设计语言进行更加涉及本质的分析 让类型化演算的类型对应到程序设计语言中的类型，就可以忠实地为类型化程序设计语言的能
11、力和局限性建模, 演 算,无类型表达式（ 项）的文法 E := x /原子表达式，x是变量（标识符） E := y. E /抽象表达式， y被称为约束变量 E := E E /应用表达式 E := (E) /括号用于改变运算次序 例如： x, y, x.x, (x.xx) (x.xx), x.(y.(xy) x) 约定： 抽象表达式的体延伸到表达式的结束或第1个不能匹配的右括号， x.xy表示x. (xy)而不是(x.x)y 并置是左结合的，如xyz表示(xy)z而不是x(yz), 演 算,变量的自由出现和约束出现 在表达式y.x(x.yx)中 y.x(x.yx)的y约束出现在y. 的体中 y
12、.x(x.yx)的x约束出现在x. 的体中 y.x(x.yx)的x并未出现在任何x. 的体中，它是一个自由出现 用FV(E)表示E中出现的自由变量集, 演 算,项的代换 x.x/xy.x(x.yx)表示y.x(x.yx)中自由出现的x 用x.x来代换，结果是y.(x.x)(x.yx) 严格定义 E/xx = E E/xE1E2 = (E/xE1)(E/xE2) E2/xx.E1 = x.E1 E2/xy.E1 = y.E2/xE1, 只要x y并且yFV(E2) E2/xy.E1 = z.E2/xz/yE1, 其中zFV(E1E2)并且y, z x E2/x(E1) = (E2/xE1), 演
13、 算,演算的变换规则 1. 变换规则 x. E = y. y/xE /约束变元x改名为y 2. 变换规则 (x. E1)E2 = E2/xE1 /可理解为函数应用到变元 3. 变换规则 x. Ex = E，只要 xFV(E) /表达函数外延性 因为对任何表达式M， (x. Ex)M = EM 注：该规则与下面的讨论关系不大, 演 算,演算的归约系统 变换规则自左向右定向，必要时可使用规则 更换约束变元的名字 定理（Church-Rosser定理） 演算的归约系统是合流的 演算的归约系统不是终止的，例如 (x. xx) (x. xx) (x. xx) (x. xx),演算中的算术,Church数
14、码 没有自由变量的表达式的含义独立于其上下文 自然数的一种有用表示 n f .x. f nx 即 0 f .x. x 1 f .x. f x 2 f .x. f (f x) 3 f .x. f (f (f x) ,演算中的算术,后继运算的定义 succ n.f. x. f (nf )x) succ 1 (n.f. x. f (nf )x) (f .x. f x) = f. x. f (f .x. f x) f )x) = f. x. f (x. f x) x) = f. x. f (f x) 2,演算中的算术,加和乘的定义 add x.y.f.z.x f (y f z) mult x.y.f
15、.x(y f ) mult 2 3 (x.y.f .x (y f) (f .x. f 2x) (f .x. f 3x) = (y.f .(f .x. f 2x) (y f) (f .x. f 3x) = f .(f .x. f 2x) ( (f .x. f 3x) f ) = f . (f .x. f 2x) (x. f 3x) = f .(x. (x. f 3x) (x. f 3x) x) ) = f .( x. (x. f 3x) (f 3x) ) = f .x. f 6x 6,演算中的算术,布尔值的编码 T x.y. x F x.y. y if_then_else x.y. z. xyz
16、 and x.y. xyF and TT (x.y. xyF)TT = TTF = T and TF (x.y. xyF)TF = TFF = F and FT (x.y. xyF)FT = FTF = F and FF (x.y. xyF)FF = FFF = F if_then_else Tpq (x.y. z. xyz)Tpq = Tpq = (x.y. x)pq = p if_then_else Fpq (x.y. z. xyz)Fpq = Fpq (x.y. y)pq = q,演算中的算术,结论 可以证明，使用表达式可定义自然数，定义自然数的加法、乘法、条件判断等，类型为NN的递归函
17、数都是表达式可定义的 其理论意义之一是，自然数算术可以可靠地嵌在演算中，因而Church-Rosser定理可以延伸到自然数算术演算中 可计算函数和演算：自然数函数F:NN是可计算函数，当且仅当存在着一个表达式f，使得对N中的每对x, y都有F(x)=y当且仅当fx=y，x和y分别是x和y的Church数码,递 归 函 数,可计算函数（直观讨论） 1. f(n) = n2 /小学生都会计算 2. q(n) = / 计算12, 22, 32, , 并与n比较, / 若k2n (k+1)2n, 结果为k 3. p(n) = 第n个素数 / 逐个检查1, 2, 3, 是否为素 / 数, 直至找到第n个
18、素数 （上述计算不仅包括加减乘除，还有比较等） 1 若在的十进制表示中有连续x个5 4. g(n) = 0 其他情况 完全无法计算,递 归 函 数,可计算函数（直观讨论） 分析计算过程，找出最简单的计算 开方：转化为平方、两数的比较、取“最后一个”例： q(n) = ,递 归 函 数,可计算函数（直观讨论） 分析计算过程，找出最简单的计算 开方：转化为平方、两数的比较、取“最后一个” 除法：转化为乘法，a/b可通过计算b1, b2, , 并同a比较 例：在函数“p(n) = 第n个素数”的计算中用到,递 归 函 数,可计算函数（直观讨论） 分析计算过程，找出最简单的计算 开方：转化为平方、两数
19、的比较、取“最后一个” 除法：转化为乘法，a/b可通过计算b1, b2, , 并同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)
20、,原始递归函数,基本函数（也称初始函数）集合 后继函数： 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, , xn1, 0) = g(x1, , xn1) f(x1, , xn1, xn+1) = h(x1, , xn1, xn, f(x1, , xn),原始递归函数,基本函数（也称初始函数）集合 后继函数： s(x) = x
21、 +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,
22、 x2, , xn) = h(g1(x1, x2, xn), g2(x1, x2, xn), gm(x1, x2, xn) 原始递归运算： f (x1, , xn1, 0) = g(x1, , xn1) f(x1, , xn1, xn+1) = h(x1, , xn1, xn, f(x1, , xn),原始递归函数,原始递归函数的定义 由中的函数通过有限次中的运算得到的函数 叫做原始递归函数 直观来看，原始递归函数显然是可以计算的 中的基本函数非常简单，经过运算后仍然是处处定义的 原始递归函数类还是相当广泛的 下面举例说明自然数上的一些函数属于原始递归函数类,原始递归函数,例1 1. ak(x
23、) = x + k (k是自然数) k次 由s(x)经过k次代入得到，即 ak(x) = s(s( s(x) 2. bk(x, y) = y + k 把y代入ak(x) ，即 bk(x, y) = ak(P2 (2)(x, y) 3. ck(x) = k 把0代入ak(x) ，即 ck(x) = ak(0) 4. dk(x1, x2, , xn) = k 把x1代入ck(x) ，即 dk(x1, x2, , xn) = ck(P1 (n)(x1, x2, , xn),原始递归函数,例2 1. f1(x, y) = x + y 由g(x) = x, h(x, y, z) = z + 1通过原始递
24、归得到，即 f1(x, 0) = x f1(x, y +1) = f1(x, y) + 1 原始递归运算： f (x1, , xn1, 0) = g(x1, , xn1) f(x1, , xn1, xn+1) = h(x1, , xn1, xn, f(x1, , xn),原始递归函数,例2 1. f1(x, y) = x + y 由g(x) = x, h(x, y, z) = z + 1通过原始递归得到，即 f1(x, 0) = x f1(x, y +1) = f1(x, y) + 1 2. f2(x, y) = x y f2(x, 0) = 0 f2(x, y +1) = f2(x, y)
25、+ x 3. f3(x, y) = xy f3(x, 0) = 1 f3(x, y +1) = x f3(x, y),递 归 函 数, 递归函数（不再深入） 由中的函数通过有限次中的运算（增加了 运 算）得到的函数叫 递归函数 原始递归函数是 递归函数的子集 例如： 递归函数不一定是完全函数, 还有，完全 的Ackermann函数不是原始递归函数 另一概念：一般递归函数 递归函数是一般递归函数 一般递归函数是 递归函数,小 结,本讲座小结 计算模型：实际计算机的高度抽象，用其解释机器的计算能力和局限性，是算法设计和算法分析的基础 概要介绍了图灵机、 演算和递归函数等经典计算模型 参考文献 1.
26、 西普塞(美)著，唐常杰等译，计算理论导引(第二 版)，机械工业出版社 2. 傅育熙，计算机科学的基础、结构与问题，中国 计算机学会通讯，6(3)，2010.3,小 结,面临问题 20世纪30年代发展起来的计算理论奠定了计算机 科学的理论基础，基于计算模型发展起来的可计算 理论、算法理论和计算复杂性理论不仅回答了“什 么是计算”，还凝练出诸如“NP=P”等重大问题 20世纪70年代以来提出的并发计算、分布计算、 网络计算、网格计算和云计算对理论提出了挑战， “什么是某某计算”和“什么是某某计算的理论模 型”等基本问题至今尚无答案。它影响到对“某某 计算的编程”等一系列理论和实际问题的深入了解,小 结,面临问题 与经典计算相比，新型计算的本质特点是交互，交互是现代计算的问题和复杂性的根源 计算机科学所面临的基本问题是：如何为经典计算与新型计算建立统一的理论框架 相关课程 可计算性和计算复杂性（现行教学计划中没有）,