经典计算的计算模型计算机科学导论五讲.ppt
《经典计算的计算模型计算机科学导论五讲.ppt》由会员分享,可在线阅读,更多相关《经典计算的计算模型计算机科学导论五讲.ppt(51页珍藏版)》请在三一文库上搜索。
1、经典计算的计算模型 计算机科学导论第五讲,计算机科学技术学院 陈意云 0551-63607043, http:/ 程 内 容,课程内容 围绕学科理论体系中的模型理论, 程序理论和计算理论 1. 模型理论关心的问题 给定模型M,哪些问题可以由模型M解决;如何比较模型的表达能力 2. 程序理论关心的问题 给定模型M,如何用模型M解决问题 包括程序设计范型、程序设计语言、程序设计、形式语义、类型论、程序验证、程序分析等 3. 计算理论关心的问题 给定模型M和一类问题, 解决该类问题需多少资源,本讲座简要介绍三种经典的抽象计算模型,2,讲 座 提 纲,基本知识 计算、计算模型、并行计算模型 图灵机概
2、述 图灵的基本思想、基本图灵机、图灵机的变种 演算 表达式的文法、 演算的变换规则、Church数码 递归函数 直观意义的可计算函数、原始递归函数、递归函数,3,基 本 知 识,计算 抽象地说,计算就是从一个符号序列 得出另一个符号序列(从 出发,在有限步内真正求出) : 12+3, : 15 /该计算是加法 : x x, : 2x /该计算是微分 : 英文句子, : 含意相同的中文句子 /翻译 : 一组公理和推理规则, : 一个定理 /定理证明 下面的f是完全定义的函数,但函数值求不出来 1 若在 的十进制表示中有连续x个5 f(x) = 0 其他情况,4,基 本 知 识,计算 不要狭隘理解
3、计算 很多非数值问题(如文字识别,图像处理等)都 可以通过转化成为数值问题来交给计算机处理(可 以在有限步骤内被解决) 不要对计算有过高预期 哥德巴赫猜想问题不属于“可计算问题”之列, 因为计算机无法给出数学意义上的证明 没有任何理由期待计算机能解决世界上所有的问 题,5,基 本 知 识,计算模型 刻画计算概念的抽象形式(formal)系统或数学系统 如图灵机、演算、递归函数和Post系统 在可计算性理论和计算复杂性理论中,计算模型 是指包括一组操作及其代价的抽象机器 可用来实现算法 可度量算法的执行时间和空间的复杂性 可分析算法需要的计算资源 可讨论算法或计算机的局限,6,基 本 知 识,并
4、行计算模型 通常指把各种(至少一类)并行计算机的基本特 征抽象出来,由此形成的抽象并行机器 对于串行计算机,全世界基本上都在使用冯诺伊 曼的计算模型;对于并行计算,一些有价值的参考 计算模型已提出,但没有一个能被大家接受的统一 的计算模型 新型计算的计算模型 云计算模型、网域(cyberspace)计算模型,7,图 灵 机 概 述,图灵的基本思想 用机器来模拟人用纸和笔进行数学计算的过程, 该过程由两类简单动作的序列构成 在纸上写出或擦除某个符号 把注意力从纸上一个位置移到另一个位置 决定下一步动作的依据:纸上某个位置的符号和 人当前的思维状态 为模拟人的这种计算过程,图灵(Turing)在2
5、0世纪 30年代构造了一种假想的简单机器,8,图 灵 机 概 述,基本图灵机,根据机器所处状态以及读写头所指符号来决定读写头的动作,有一个状态寄存器,9,图 灵 机 概 述,基本图灵机 T= Q, , b, , q0, F, Q: 有穷非空的状态集 : 有穷非空的带符号集 b: 空白符号 b: 输入符号集 q0Q: 开始状态 FQ: 终止状态集 :(QF ) Q L, R: 迁移函数, L和R表 示读写头的左右移 例如: (q0, 0)(q1, X, R), (q1, 1)(q2, Y, L),10,图 灵 机 概 述,例: 识别语言 L=0n1n | n 1 的图灵机 策略:从左向右, 轮番
6、把带上最左的0和1分别写成X和Y(期间要向右 和向左移动读写头),直至全部写完 T= Q, , b, , q0, F, Q = q0, q1, , q5 = 0, 1, b, X, Y = 0, 1 F = q5 见下一页,11,图 灵 机 概 述,例: 识别语言 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,
7、Y)(q2, Y, L) (q3, B)(q5, Y, R) (q2, X)(q3, X, R),12,图 灵 机 概 述,例: 识别语言 L=0n1n | n 1 的图灵机 识别000111的动作 (q0, 0)(q1, X, R),动作之前的状况,动作之后的状况,13,图 灵 机 概 述,例: 识别语言 L=0n1n | n 1 的图灵机 识别000111的动作 (q0, 0)(q1, X, R) (q1, 0)(q1, 0, R),动作之前的状况,动作之后的状况,14,图 灵 机 概 述,例: 识别语言 L=0n1n | n 1 的图灵机 识别000111的动作 (q0, 0)(q1,
8、X, R) (q1, 0)(q1, 0, R) (q1, 0)(q1, 0, R),动作之前的状况,动作之后的状况,15,图 灵 机 概 述,例: 识别语言 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),动作之前的状况,动作之后的状况,16,图 灵 机 概 述,例: 识别语言 L=0n1n | n 1 的图灵机 识别000111的动作 (q0, 0)(q1, X, R) (q1, 0)(q1, 0, R) (q1, 0)(q1, 0, R
9、) (q1, 1)(q2, Y, L) (q2, 0)(q4, 0, L),动作之前的状况,动作之后的状况,17,图 灵 机 概 述,例: 识别语言 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),动作之前的状况,动作之后的状况,18,图 灵 机 概 述,例: 识别语言 L=0n1n | n 1 的图灵机 识别000111的动作 (q0, 0)(q1, X, R) (q
10、1, 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),动作之前的状况,动作之后的状况,19,图 灵 机 概 述,例: 识别语言 L=0n1n | n 1 的图灵机 识别000111的动作 (q0, 0)(q1, X, R),然后又从q0 继续,动作之前的状况,20,图 灵 机 概 述,图灵机的变种 纸带两端都可以无限伸展 多道图灵机 图灵机的带被 分成k道 可看成带上的 符号被分成k元组,21,图 灵 机 概 述,图灵机的变种 纸带两端都
11、可以无限伸展 多道图灵机 多带图灵机 k条带, 双向无穷 有限控制器上有 k个带头 独立地左移或右移 每个带头一个单元或 保持不动,22,图 灵 机 概 述,图灵机的变种 纸带两端都可以无限伸展 多道图灵机 多带图灵机 不确定图灵机,等等 它们的计算能力都等价于基本图灵机 图灵机的计算能力 等价于下面讨论演算和递归函数,23, 演 算,演算的历史 邱奇(Church)在20世纪30年代研究的定义可计算函数的一种形式体系 克莱尼(Kleene)在1936年证明,可定义的所有自然数函数正好是所有的递归函数 图灵在1937年证明,可定义的数值函数正好是图灵机可计算的函数 起初演算是无类型的,因在基于
12、无类型演算的逻辑中发现一个悖论,导致类型化演算的研究 演算一直影响着程序设计语言的研究,24, 演 算,演算和程序设计语言 20世纪50年代,无类型演算明显影响了Lisp语言的研究 20世纪60年代认识到,程序设计语言的语义可以通过使用拓展的演算给出 现代的观点认为,类型化演算引导对程序设计语言进行更加涉及本质的分析 让类型化演算的类型对应到程序设计语言中的类 型,就可以忠实地为类型化程序设计语言的能力和 局限性建模,25, 演 算,无类型表达式E( 项)的文法 E := x /原子表达式,x是变量(标识符) E := y. E /抽象表达式, y被称为约束变量 E := E E /应用表达式
13、(函数应用到变元) 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),26, 演 算,变量的自由出现和约束出现 在表达式y.x(x.yx)中 y.x(x.yx)的y约束出现在y. 的体中 y.x(x.yx)的x约束出现在x. 的体中 y.x(x.yx)的x并未出现在任何x. 的体中,它是自由出现的x 用FV(E)表示E中出现的自由变量(free va
14、riable)集,27, 演 算,项的代换 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),28, 演 算,演算的变换规则 1. 变换规则 x. E = y. y/xE /约束变元x改名为y 2. 变换规则 (x. E1)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 经典 计算 模型 计算机科学 导论
链接地址:https://www.31doc.com/p-3171042.html