经典计算的计算模型计算机科学导论第五讲

《经典计算的计算模型计算机科学导论第五讲》由会员分享，可在线阅读，更多相关《经典计算的计算模型计算机科学导论第五讲（47页珍藏版）》请在金锄头文库上搜索。

1、经典计算的计算模型经典计算的计算模型计算机科学导论第五讲计算机科学导论第五讲计算机科学技术学院计算机科学技术学院陈意云陈意云0551-脉棒处狱试船诫蚊哉芽串鸿娇搭叔可绘择喉愁掏待铸素耻拧蔫涌筛脐咋践经典计算的计算模型计算机科学导论第五讲经典计算的计算模型计算机科学导论第五讲课课 程程 内内 容容课程内容课程内容围绕学科理论体系中的模型理论围绕学科理论体系中的模型理论, 程序理论和计算理论程序理论和计算理论1. 模型理论关心的问题模型理论关心的问题 给定模型给定模型M，哪些问题可以由模型，哪些问题可以由模型M解决；如何解决；如何比较模型的表达能力比较模型的表达能力2. 程序理论关心的问题程序理论

2、关心的问题给定模型给定模型M，如何用模型，如何用模型M解决问题解决问题包括程序设计范型、程序设计语言、程序设计、包括程序设计范型、程序设计语言、程序设计、形式语义、类型论、程序验证、程序分析等形式语义、类型论、程序验证、程序分析等3. 计算理论关心的问题计算理论关心的问题给定模型给定模型M和一类问题和一类问题, 解决该类问题需多少资源解决该类问题需多少资源夺掩吁传拢容被辛梢停纺匝邑涪嚎舆动泻掸滩湃盼斗幻链等技完慰渭栓耶经典计算的计算模型计算机科学导论第五讲经典计算的计算模型计算机科学导论第五讲讲讲 座座 提提 纲纲基本知识基本知识计算、计算模型、并行计算模型计算、计算模型、并行计算模型图灵机概

3、述图灵机概述图灵的基本思想、基本图灵机、图灵机的变种图灵的基本思想、基本图灵机、图灵机的变种 演算演算 表达式的文法、表达式的文法、 演算的变换规则、演算的变换规则、Church数码数码递归函数递归函数直观意义的可计算函数、原始递归函数、递归函直观意义的可计算函数、原始递归函数、递归函数数爹敏掠钢性拈咽聚拣匹匪津坤念既檬破降推增爸乳宵湛之嘴撵肘溶萌蹦号经典计算的计算模型计算机科学导论第五讲经典计算的计算模型计算机科学导论第五讲基基 本本 知知 识识计算算 抽象地说，计算就是从一个符号序列抽象地说，计算就是从一个符号序列 得出另一得出另一个符号序列个符号序列 （从（从 出发，在有限步内真正求出出

4、发，在有限步内真正求出 ） : 12+3, : 15/该计算是加法该计算是加法 : x x, : 2x /该计算是该计算是微分微分 : 英文句子英文句子, : 含意相同的中文句子含意相同的中文句子 /翻译翻译 : 一一组公理和推理规则组公理和推理规则, : 一个定理一个定理 /定理证明定理证明下面的下面的f是完全定义的函数，但函数值求不出来是完全定义的函数，但函数值求不出来 1 若在若在 的十进制表示中有连续的十进制表示中有连续x个个5 f(x) = 0 其他情况其他情况宝甘串遇辙壁阎采巢冶擂砧凛泉晕榆嫉体涡疙憨择瘟遥皮金抹制此疤砰资经典计算的计算模型计算机科学导论第五讲经典计算的计算模型计算

5、机科学导论第五讲基基 本本 知知 识识计算算不要狭隘理解计算不要狭隘理解计算很多非数值问题（如文字识别，图像处理等）都很多非数值问题（如文字识别，图像处理等）都可以通过转化成为数值问题来交给计算机处理（可可以通过转化成为数值问题来交给计算机处理（可以在有限步骤内被解决）以在有限步骤内被解决）不要对计算有过高预期不要对计算有过高预期哥德巴赫猜想问题不属于哥德巴赫猜想问题不属于“可计算问题可计算问题”之列，之列，因为计算机无法给出数学意义上的证明因为计算机无法给出数学意义上的证明没有任何理由期待计算机能解决世界上所有的问没有任何理由期待计算机能解决世界上所有的问题题稳悔蚜首枝岳唯砖献朋单捣嚎染蔫何

6、呈沉卜返捐邮盾嗓脉竖躬煎沪狙土泊经典计算的计算模型计算机科学导论第五讲经典计算的计算模型计算机科学导论第五讲基基 本本 知知 识识计算模型算模型刻画计算概念的抽象形式系统或数学系统刻画计算概念的抽象形式系统或数学系统如图灵机、如图灵机、 演算、递归函数和演算、递归函数和Post系统系统在可在可计算性理算性理论和和计算复算复杂性理性理论中，中，计算模型算模型 是指包括一是指包括一组操作及其代价的抽象机器操作及其代价的抽象机器 可用来可用来实现算法算法 可度量算法的可度量算法的执行行时间和空和空间的复的复杂性性 可分析算法需要的可分析算法需要的计算算资源源 可可讨论算法或算法或计算机的局限算机的局

7、限仙咕综痹揽呐夺槽酥屹晨湖疵猖舆茫肃舒靠察椰捧蛆瀑租询猛刺斗奋钎随经典计算的计算模型计算机科学导论第五讲经典计算的计算模型计算机科学导论第五讲基基 本本 知知 识识并行并行计算模型算模型通常指把各种（至少一类）并行计算机的基本特通常指把各种（至少一类）并行计算机的基本特征抽象出来，形成的抽象并行机器征抽象出来，形成的抽象并行机器对于串行计算机，全世界基本上都在使用冯对于串行计算机，全世界基本上都在使用冯诺伊诺伊曼的计算模型；对于并行计算，一些有价值的参考曼的计算模型；对于并行计算，一些有价值的参考计算模型已提出，但没有一个能被大家接受的统一计算模型已提出，但没有一个能被大家接受的统一的计算模型

8、的计算模型新型新型计算的算的计算模型算模型网域计算模型、云计算模型、海计算模型网域计算模型、云计算模型、海计算模型盐讼笨孤魔忘温坎兴篆牙诺挪飘等割另搏恭七耐扇童隧癣挟灿孕治震惟供经典计算的计算模型计算机科学导论第五讲经典计算的计算模型计算机科学导论第五讲图图 灵灵 机机 概概 述述图灵的基本思想灵的基本思想用机器来模用机器来模拟人用人用纸和笔和笔进行数学行数学计算的算的过程，程，该过程由两程由两类简单动作的序列构成作的序列构成在在纸上写出或擦除某个符号上写出或擦除某个符号把注意力从把注意力从纸上一个位置移到另一个位置上一个位置移到另一个位置决定下一步决定下一步动作的依据：作的依据：纸上某个位置

9、的符号和上某个位置的符号和人当前的思人当前的思维状状态为模模拟人的人的这种种计算算过程，程，图灵在灵在20世世纪30年代年代构造了一种假想的构造了一种假想的简单机器机器阴披蓟真涌陕双缕蔫棘铅析栽惰村匀乖起儒恼博轰诱酗霸浸汐渺帝茬挡券经典计算的计算模型计算机科学导论第五讲经典计算的计算模型计算机科学导论第五讲图图 灵灵 机机 概概 述述基本基本图灵机灵机T= Q, , b, , q0, F, Q: 有有穷非空的状非空的状态集集 : 有有穷非空的非空的带符号集符号集b: 空白符号空白符号 b: 输入符号集入符号集q0 Q: 开始状开始状态F Q: 终止状止状态集集 :(QF ) Q L, R: 迁

10、移函数，迁移函数， L和和R表表示示读写写头的左右移的左右移例如：例如： (q0, 0)(q1, X, R), (q1, 1)(q2, Y, L) a1a2 ai anbb有限有限控制器控制器纸带纸带读写头读写头蓝串欺侮烘毖啸傲涂椭亏森辫獭淑留陋歼吝浩握亭昌专茹办隶涡屈挫蚤葱经典计算的计算模型计算机科学导论第五讲经典计算的计算模型计算机科学导论第五讲图图 灵灵 机机 概概 述述例：例：识别语言言L=0n1n | n 1的的图灵机灵机策略：从左向右策略：从左向右轮番把番把带上最左的上最左的0和和1分分别写成写成X和和Y（期（期间要向右和要向右和向左移向左移动读写写头），直至全部写完），直至全部写

11、完T= Q, , b, , q0, F, Q = q0, q1, , q5 = 0, 1, b, X, Y = 0, 1 F = q5 见下一下一页000111bb有限有限控制器控制器集便土鸳擦项坟钵诬窥蛙氯届蔡仆谩练亡栈焦轩桐郭健预焙景梧疼岿菏淖经典计算的计算模型计算机科学导论第五讲经典计算的计算模型计算机科学导论第五讲图图 灵灵 机机 概概 述述例：例：识别语言言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,

12、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)000111bb有限有限控制器控制器译岿爷低画惦勇纺莽埔恋杉娄妇云琢涟顾婆电哉锥包狭痢鲁狱弟订蚂猪酋经典计算的计算模型计算机科学导论第五讲经典计算的计算模型计算机科学导论第五讲图图 灵灵 机机 概概 述述例：例：识别语言言L=0n1n | n 1的的图灵机灵机 识别000111的的动作作 (q0, 0)(q1, X, R) 000111bb有限有限控制器控制器X00111bb有限有限控制器控制

13、器店句村些皂沈古幌候阴针锰摆煌粤烯拽炊权瑰纺户竞筷旋农粥至剪搜亮纷经典计算的计算模型计算机科学导论第五讲经典计算的计算模型计算机科学导论第五讲图图 灵灵 机机 概概 述述例：例：识别语言言L=0n1n | n 1的的图灵机灵机 识别000111的的动作作 (q0, 0)(q1, X, R) (q1, 0)(q1, 0, R) X00111bb有限有限控制器控制器X00111bb有限有限控制器控制器坝影互也森陶那寸感束香到磋藻夸火封岔康描疵令智阳嚣基烁辖雷惨诞削经典计算的计算模型计算机科学导论第五讲经典计算的计算模型计算机科学导论第五讲图图 灵灵 机机 概概 述述例：例：识别语言言L=0n1n

14、| n 1的的图灵机灵机 识别000111的的动作作 (q0, 0)(q1, X, R) (q1, 0)(q1, 0, R) (q1, 0)(q1, 0, R) X00111bb有限有限控制器控制器X00111bb有限有限控制器控制器因卷窘尽磅猩壕解裕帐览儿早理饵牲埔知并盼羌贞谅豹孤泉仿醚糖在佑绚经典计算的计算模型计算机科学导论第五讲经典计算的计算模型计算机科学导论第五讲图图 灵灵 机机 概概 述述例：例：识别语言言L=0n1n | n 1的的图灵机灵机 识别000111的的动作作 (q0, 0)(q1, X, R) (q1, 0)(q1, 0, R) (q1, 0)(q1, 0, R) (q

15、1, 1)(q2, Y, L) X00Y11bb有限有限控制器控制器X00111bb有限有限控制器控制器猴益椒肾锰噎滥脑探庆居系八枯带铅刘刨媒牺题儒拿纯月再证叔草条选兄经典计算的计算模型计算机科学导论第五讲经典计算的计算模型计算机科学导论第五讲图图 灵灵 机机 概概 述述例：例：识别语言言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)X00Y11bb有限有限控制器控制器X00Y11bb有限有限控制

16、器控制器与诵姻财咆尺咋踢涧顽饼辞闺篷邱朵婴毅粟谩枷裁帧玄驭崎害鹏嘶亥敬嗅经典计算的计算模型计算机科学导论第五讲经典计算的计算模型计算机科学导论第五讲图图 灵灵 机机 概概 述述例：例：识别语言言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)X00Y11bb有限有限控制器控制器X00Y11bb有限有限控制器控制器撩昔涪揍清烈真恋籽沼慌溜柠捌饺瑟嗣肇棍霄诧对娶助靴察

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) (q4, X)(q0, X, R)X00Y11bb有限有限控制器控制器X00Y11bb有限有限控制器控制器然后又从然后又从q0 继续沉阎旭专微滤铬赶唉苹撅星煮始耪晕窿潞镀迭颤补轩绚王

18、国蔼蟹攀区封懦经典计算的计算模型计算机科学导论第五讲经典计算的计算模型计算机科学导论第五讲图图 灵灵 机机 概概 述述图灵机的变种图灵机的变种纸带两端都可以无限伸展纸带两端都可以无限伸展多道图灵机多道图灵机多带图灵机多带图灵机不确定图灵机，等等不确定图灵机，等等它们的计算能力都等价于基本图灵机它们的计算能力都等价于基本图灵机图灵机的计算能力图灵机的计算能力等价于下面讨论等价于下面讨论 演算和递归函数演算和递归函数袋岸六假载概险扦臂栖贱铝范湾写蚊硫叼遮汝栖鄙尤蔓艺又钓盈倪贝肛秀经典计算的计算模型计算机科学导论第五讲经典计算的计算模型计算机科学导论第五讲 演演 算算 演算的历史演算的历史Churc

19、h在在20世纪世纪30年代研究的定义可计算函数的年代研究的定义可计算函数的一种形式体系一种形式体系Kleene在在1936年证明，年证明， 可可定义的所有自然数函数定义的所有自然数函数正好是所有的递归函数正好是所有的递归函数Turing在在1937年证明，年证明， 可定义的数值函数正好是可定义的数值函数正好是Turing机可计算的函数机可计算的函数起初起初 演算是无类型的，因在基于无类型演算是无类型的，因在基于无类型 演算的演算的逻辑中发现一个悖论，导致类型化逻辑中发现一个悖论，导致类型化 演算的研究演算的研究 演算一直影响着程序设计语言的研究演算一直影响着程序设计语言的研究旭主梨词伴册裕妈侮

20、臃汲寡座焦破驱芽趣掠奴滤琶巡刮富寥陶扣墒丈鲤臆经典计算的计算模型计算机科学导论第五讲经典计算的计算模型计算机科学导论第五讲 演演 算算 演算和程序设计语言演算和程序设计语言20世纪世纪50年代，无类型年代，无类型 演算明显影响了演算明显影响了Lisp语言语言的研究的研究20世纪世纪60年代认识到，程序设计语言的语义可以年代认识到，程序设计语言的语义可以通过使用拓展的通过使用拓展的 演算给出演算给出现代的观点认为，类型化现代的观点认为，类型化 演算引导对程序设计语演算引导对程序设计语言进行更加涉及本质的分析言进行更加涉及本质的分析让类型化让类型化 演算的类型对应到程序设计语言中的类演算的类型对应

21、到程序设计语言中的类型，就可以忠实地为类型化程序设计语言的能力型，就可以忠实地为类型化程序设计语言的能力和局限性建模和局限性建模法屹廊欢归向神熟务被职缓政溃痊腾趋烽杰搽壮幅斡珠苇收县剩县噬昂色经典计算的计算模型计算机科学导论第五讲经典计算的计算模型计算机科学导论第五讲 演演 算算无类型无类型 表达式（表达式（ 项）的文法项）的文法E := x/原子表达式，原子表达式，x是变量（标识符）是变量（标识符）E := y. E/抽象表达式，抽象表达式， y被称为约束变量被称为约束变量E := E E/应用表达式应用表达式E := (E) /括号用于改变运算次序括号用于改变运算次序例如：例如：x, y,

22、 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.

23、yx)的的y约束出现在约束出现在 y. 的体中的体中 y.x( x.yx)的的x约束出现在约束出现在 x. 的体中的体中 y.x( x.yx)的的x并未出现在任何并未出现在任何 x. 的体中，它是的体中，它是一个自由出现一个自由出现用用FV(E)表示表示E中出现的自由变量集中出现的自由变量集伦遏脉店拍霄炕丝逞殊骨糖傈国沃助口蹭伟安篡衍炬魔券疗蔡鸳诣挛食褒经典计算的计算模型计算机科学导论第五讲经典计算的计算模型计算机科学导论第五讲 演演 算算项的代换项的代换 x.x/x y.x( x.yx)表示表示 y.x( x.yx)中自由出现的中自由出现的x用用 x.x来代换，结果是来代换，结果是 y.(

24、x.x)( x.yx)严格定义严格定义E/xx = EE/xE1E2 = (E/xE1)(E/xE2)E2/x x.E1 = x.E1 E2/x y.E1 = y.E2/xE1, 只要只要x y并且并且y FV(E2)E2/x y.E1 = z.E2/xz/yE1, 其中其中z FV(E1E2)并且并且y, z xE2/x(E1) = (E2/xE1) 琉抨更迄奈期千贬卤劫翟喻恕瑶搜镍丘敢告衍俏幼咏渺屉蔽讶洋折车抵湖经典计算的计算模型计算机科学导论第五讲经典计算的计算模型计算机科学导论第五讲 演演 算算 演算的变换规则演算的变换规则1. 变换规则变换规则 x. E = y. y/xE /约束变

25、元约束变元x改名为改名为y2. 变换规则变换规则 ( x. E1)E2 = E2/xE1 /可理解为函数应用到变元可理解为函数应用到变元3. 变换规则变换规则 x. Ex = E，只要，只要 x FV(E) /表达函数外延性表达函数外延性因为对任何表达式因为对任何表达式M， ( x. Ex)M = EM注：该规则与下面的讨论关系不大注：该规则与下面的讨论关系不大州版已娩戒稗示澳膜货盲潮翱秦绍模刽雀荤粘伎董莱杠卿泰涣镊起陀蒸测经典计算的计算模型计算机科学导论第五讲经典计算的计算模型计算机科学导论第五讲 演演 算算 演算的归约系统演算的归约系统 变换规则自左向右定向，必要时可使用变换规则自左向右定

26、向，必要时可使用 规则规则更换约束变元的名字更换约束变元的名字定理（定理（Church-Rosser定理）定理） 演算的归约系统是合流的演算的归约系统是合流的 演算的归约系统不是终止的，例如演算的归约系统不是终止的，例如 ( x. xx) ( x. xx) ( x. xx) ( x. xx) 庚篱岁宠畅前愈戊殆左杖汪库耸扒喝顾允纤枕声妆瘟壁厨窿盈坞挂傀侈袜经典计算的计算模型计算机科学导论第五讲经典计算的计算模型计算机科学导论第五讲 演算中的算术演算中的算术Church数码数码没有自由变量的没有自由变量的 表达式的含义独立于其上下文表达式的含义独立于其上下文自然数的一种有用表示自然数的一种有用表

27、示 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.

28、f (f x) 2驴歇敢铅弥返红刽陀雁柔室设舟亦诗辐灰坠馏魏奇绿硷乞吨阵灵屎绿泣胳经典计算的计算模型计算机科学导论第五讲经典计算的计算模型计算机科学导论第五讲 演算中的算术演算中的算术加和乘的定加和乘的定义义add x. y. f. z.x f (y f z)mult x. y. f .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 . (

29、 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. xF x. y. yif_then_else x. y. z. xyzand x. y. xyFand TT ( x. y. xyF)TT = TTF = Tand TF ( x. y.

30、 xyF)TF = TFF = Fand FT ( x. y. xyF)FT = FTF = Fand 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砂幻尺褪谐憋瘸酒椰醚挣茵拢绵都拌崩介谢试曝儒匪枫可跺汰峰簧鹰阀灰经典计算的计算模型计算机科学导论第五讲经典计算的计算模型计算机科学导论第五讲 演算中的算术演算中的算术结论结论可可以以证证明明，使使用用

31、表表达达式式可可定定义义自自然然数数，定定义义自自然然数数的的加加法法、乘乘法法、条条件件判判断断等等，类类型型为为N NN N的的递递归函数都是归函数都是 表达式可定义的表达式可定义的其其理理论论意意义义之之一一是是，自自然然数数算算术术可可以以可可靠靠地地嵌嵌在在 演演算算中中，因因而而Church-Rosser定定理理可可以以延延伸伸到到自自然然数算术演算中数算术演算中可可计计算算函函数数和和 演演算算：自自然然数数函函数数F:N NN N是是可可计计算算函函数数，当当且且仅仅当当存存在在着着一一个个 表表达达式式f，使使得得对对N N中中的的每每对对x, y都都有有F(x)=y当当且且

32、仅仅当当fx =y ，x 和和y 分别是分别是x和和y的的Church数码数码坊谢沿侵六至画盛殃诲祷掺第屡扣课绩捧术异奄婚娥涟误钙显丽滚刀闯讹经典计算的计算模型计算机科学导论第五讲经典计算的计算模型计算机科学导论第五讲递递 归归 函函 数数可计算函数（直观讨论）可计算函数（直观讨论）1. f(n) = n2/小学生都会计算小学生都会计算2. q(n) = / 计算计算12, 22, 32, , 并与并与n比较比较, / 若若k2 n (k+1)2n, 结果为结果为k3. p(n) = 第第n个素数个素数 / 逐个检查逐个检查1, 2, 3, 是否为素是否为素/ 数数, 直至找到第直至找到第n个

33、素数个素数（上述计算不仅包括加减乘除，还有比较等）（上述计算不仅包括加减乘除，还有比较等） 1 若在若在 的十进制表示中有连续的十进制表示中有连续x个个54. g(n) = 0 其他情况其他情况完全无法计算完全无法计算 n莆钡乳均晕右盎探肪裳例惕僳舒诬宿朗羔械掐幕眉黍赠佛察妻磷魏劈驰坊经典计算的计算模型计算机科学导论第五讲经典计算的计算模型计算机科学导论第五讲递递 归归 函函 数数可计算函数（直观讨论）可计算函数（直观讨论）分析计算过程，找出最简单的计算分析计算过程，找出最简单的计算开方：转化为平方、两数的比较、取开方：转化为平方、两数的比较、取“最后一个最后一个”例：例： q(n) = n卸

34、凑常名诬艾萌踌体坯求宠佰栽首郁闯盟温野京铲式沉锋好彻索盗盘殆话经典计算的计算模型计算机科学导论第五讲经典计算的计算模型计算机科学导论第五讲递递 归归 函函 数数可计算函数（直观讨论）可计算函数（直观讨论）分析计算过程，找出最简单的计算分析计算过程，找出最简单的计算开方：转化为平方、两数的比较、取开方：转化为平方、两数的比较、取“最后一个最后一个”除法：转化为乘法，除法：转化为乘法，a/b可通过计算可通过计算b 1, b 2, ,并同并同a比较比较例：在函数例：在函数“p(n) = 第第n个素数个素数”的计算中用到的计算中用到瞳苯蛰甭遗葡旬翠胖绝家叙谜既衅比萧酚浑烙缩拟舜场诡赵坡训疾夏桔盘经典计

35、算的计算模型计算机科学导论第五讲经典计算的计算模型计算机科学导论第五讲递递 归归 函函 数数可计算函数（直观讨论）可计算函数（直观讨论）分析计算过程，找出最简单的计算分析计算过程，找出最简单的计算开方：转化为平方、两数的比较、取开方：转化为平方、两数的比较、取“最后一个最后一个”除法：转化为乘法，除法：转化为乘法，a/b可通过计算可通过计算b 1, b 2, ,并同并同a比较比较乘法：转化为加法乘法：转化为加法加法：转化为加加法：转化为加1运算运算 一般的计算过程究竟能转化为哪些最基本计算的一般的计算过程究竟能转化为哪些最基本计算的计算过程？计算过程？疆所罩伶讹谷矮导录服滦沂饼供驻法兢菊漠策坎

36、挎瞪凡毙豫猎纂还喳搅维经典计算的计算模型计算机科学导论第五讲经典计算的计算模型计算机科学导论第五讲原始递归函数原始递归函数基本函数（也称初始函数）集合基本函数（也称初始函数）集合后继函数：后继函数：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)

37、莎昌呜峡挂然传假膝参弹身币悍躬饯梁袋看了套絮珍捅纸都缓姿姆辗皆抄经典计算的计算模型计算机科学导论第五讲经典计算的计算模型计算机科学导论第五讲原始递归函数原始递归函数基本函数（也称初始函数）集合基本函数（也称初始函数）集合后继函数：后继函数：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, ,

38、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, , x

39、n) =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

40、 (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)震椽谊茫作枚帕斑湾粉又套蓉粉淮萧执赏题盏阁犊飞擦脱谓产姑狄霉邱完经典计算的计算模型计算机科学导论第五讲经典计算的计算模型计算机科学导论第五讲原始递归函数原始递归函数原始递归函数的定义原始递归函数的定义由由中的

41、函数通过有限次中的函数通过有限次中的运算得到的函数中的运算得到的函数叫做原始递归函数叫做原始递归函数直观来看，原始递归函数显然是可以计算的直观来看，原始递归函数显然是可以计算的中中的的基基本本函函数数非非常常简简单单，经经过过运运算算后后仍仍然然是是处处处定义的处定义的原始递归函数类还是相当广泛的原始递归函数类还是相当广泛的下下面面举举例例说说明明自自然然数数上上的的一一些些函函数数属属于于原原始始递递归归函数类函数类焚豪逃栅淆愧琅辣酿娱料小止匠高嚷蹬抵舵沙其末诺宙淳玩助解虾舅风循经典计算的计算模型计算机科学导论第五讲经典计算的计算模型计算机科学导论第五讲原始递归函数原始递归函数例例11. a

42、k(x) = 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)睛摇猴伴搞稿租络毁臭泽坎彩萧坎邦幽臀禁没稽殴钨胎汹敦戍竿梳侦杯浚经典计算的计

43、算模型计算机科学导论第五讲经典计算的计算模型计算机科学导论第五讲原始递归函数原始递归函数例例21. 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原始递归运算：原始递归运算： f (x1, , xn 1, 0) = g(x1, , xn 1) f(x1, , xn 1, xn+1) = h(x1, , xn 1, xn, f(x1, , xn)棠掩包揽挫蛆江撂顽查扒耳豆羞搬拱切拍为别革民胶匆刮布槽谆阁伶垫既经典计算的计算模型计算机

44、科学导论第五讲经典计算的计算模型计算机科学导论第五讲原始递归函数原始递归函数例例21. 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) + 12. f2(x, y) = x y f2(x, 0) = 0 f2(x, y +1) = f2(x, y) + x3. f3(x, y) = xy f3(x, 0) = 1 f3(x, y +1) = x f3(x, y)粕撅千溯潭撇越弱到烙鳃雏母遏式送摩祸曰詹仙秋岔诀涸丘缄雄脚嚼造着经典计算的计算

45、模型计算机科学导论第五讲经典计算的计算模型计算机科学导论第五讲递递 归归 函函 数数 递归函数（不再深入）递归函数（不再深入）由由中中的的函函数数通通过过有有限限次次中中的的运运算算（增增加加了了 运运算）得到的函数叫算）得到的函数叫 递归函数递归函数原始递归函数是原始递归函数是 递归函数的子集递归函数的子集例如：例如： 递归函数不一定是完全函数递归函数不一定是完全函数, 还有，完全还有，完全的的Ackermann函数不是原始递归函数函数不是原始递归函数另一概念：一般递归函数另一概念：一般递归函数 递归函数是一般递归函数递归函数是一般递归函数一般递归函数是一般递归函数是 递归函数递归函数农黍扳

46、醉痉筒竟遭臃全恬舵惯蒲仲湖帘见敌灾奇猫臂龚密锣敷锑征攘低早经典计算的计算模型计算机科学导论第五讲经典计算的计算模型计算机科学导论第五讲小小 结结本讲座小结本讲座小结计计算算模模型型：实实际际计计算算机机的的高高度度抽抽象象，用用其其解解释释机机器器的的计计算算能能力力和和局局限限性性，是是算算法法设设计计和和算算法法分分析析的基础的基础概概要要介介绍绍了了图图灵灵机机、 演演算算和和递递归归函函数数等等经经典典计计算模型算模型参考文献参考文献1. 西普塞西普塞(美美)著，唐常杰等译，计算理论导引著，唐常杰等译，计算理论导引(第二第二版版)，机械工业出版社，机械工业出版社2. 傅育熙，计算机科学

47、的基础、结构与问题，中国傅育熙，计算机科学的基础、结构与问题，中国计算机学会通讯，计算机学会通讯，6(3)，2010.3昼统争泼饯汽鲸疼老笨蒂姓萝钡诱哩彦醇鹰涤博疆芥捡羹哲磷让詹途岳瞄经典计算的计算模型计算机科学导论第五讲经典计算的计算模型计算机科学导论第五讲小小 结结面临问题面临问题20世纪世纪30年代发展起来的计算理论奠定了计算机年代发展起来的计算理论奠定了计算机科学的理论基础，基于计算模型发展起来的可计算科学的理论基础，基于计算模型发展起来的可计算理论、算法理论和计算复杂性理论不仅回答了理论、算法理论和计算复杂性理论不仅回答了“什什么是计算么是计算”，还凝练出诸如，还凝练出诸如“NP=P

48、”等重大问题等重大问题20世纪世纪70年代以来提出的并发计算、分布计算、年代以来提出的并发计算、分布计算、网络计算、网格计算和云计算对理论提出了挑战，网络计算、网格计算和云计算对理论提出了挑战，“什么是某某计算什么是某某计算”和和“什么是某某计算的理论模什么是某某计算的理论模型型”等基本问题至今尚无答案。它影响到对等基本问题至今尚无答案。它影响到对“某某某某计算的编程计算的编程”等一系列理论和实际问题的深入了解等一系列理论和实际问题的深入了解峭窜智兔鞠害恨瑰急尊伸晒电锯碱慑戎岂柔皂赫机皆椿帧租阶惦旭拇饱惨经典计算的计算模型计算机科学导论第五讲经典计算的计算模型计算机科学导论第五讲小小 结结面临问题面临问题与与经经典典计计算算相相比比，新新型型计计算算的的本本质质特特点点是是交交互互，交互是现代计算的问题和复杂性的根源交互是现代计算的问题和复杂性的根源计计算算机机科科学学所所面面临临的的基基本本问问题题是是：如如何何为为经经典典计计算与新型计算建立统一的理论框架算与新型计算建立统一的理论框架相关课程相关课程可计算性和计算复杂性（现行教学计划中没有）可计算性和计算复杂性（现行教学计划中没有）乙玲茨摧翰扫赔兆骚途氧郡凌辫封未苗踌慈纷恿掳咋含憎泣兼他登毫搅伦经典计算的计算模型计算机科学导论第五讲经典计算的计算模型计算机科学导论第五讲