第2章程序算法与图灵机模型精选文档.ppt

《第2章程序算法与图灵机模型精选文档.ppt》由会员分享，可在线阅读，更多相关《第2章程序算法与图灵机模型精选文档.ppt（44页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第2章程序算法与图灵机模型本讲稿第一页，共四十四页2.1 算法什么是算法？指完成一个任务所需要的具体步骤和方法。即给定初始状态或输入数据，经过计算机程序的有限次运算，能够得出所要求或期望的终止状态或输出数据。本讲稿第二页，共四十四页算法的特点：(1)有穷性 算法中每一条指令的执行次数有限，执行每条指令的时间有限。(对任何的合法输入，算法总能在运算有限步后终止)(2)确定性 组成算法的每条指令是清晰的，无歧义的。(3)输入 一个算法有零个或多个输入。(4)输出 一个算法至少产生一个量作为输出。(5)可行性 算法中的运算是能够实现的基本运算，每一种运算可在有限的时间内完成。本讲稿第三页，共四十四页

2、一些经典的算法 思考：求两个数的最大公约数如何实现？P27排序之冒泡排序(在排序过程中总是小数往前放，大数往后放，相当于气泡往上升)二分法之求函数的解(对于函数f(x),如果存在实数c,当x=c时，若f(c)=0,那么把x=c叫做函数f(x)的零点。解方程即要求f(x)的所有零点。)本讲稿第四页，共四十四页1365和3654 两数的最大公约数？步骤：36541365 给出余数9241365924 给出余数441924441 给出余数4244142 给出余数214221 给出余数0。因此，用于做除数的21即是所需要的最大公约数。本讲稿第五页，共四十四页欧几里德算法逻辑运算的流程图欧几里德算法逻辑

3、运算的流程图 连续减法找到除法余数的流程图连续减法找到除法余数的流程图 本讲稿第六页，共四十四页图灵“机”是一段“抽象数学”，是一种抽象计算模型（通用计算模型）而不是一个物理对象。用来精确定义可计算函数部分可计算函数与可计部分可计算函数与可计算函数算函数。其目的是为了解决称为判决问题判决问题的一个范围广阔的问题。通过研究图灵机，来研究递归可枚举集（recursively enumerable）和部分递归函数（partial recursive function）对算法和可计算性进行研究提供形式化描述工具。2.2 图灵机模型本讲稿第七页，共四十四页图灵机缘起1900,德国数学家希尔伯特(D.Hi

4、lbert)在巴黎第二届数学家大会上提出23个数学难题中,逻辑的完备性问题,即是否所有数学问题原则上都可解.1936,英国数学家图灵“论可计算数及其在判定问题中的应用”(On Computable Numbers With an Application to the Entscheidungs Problem)结论：可解的问题是能够用图灵机的自动机理论模型表达的问题.本讲稿第八页，共四十四页希尔伯特第十问题数学问题的一般算法步骤问题（原则上是否存在一般数学问题的解题步骤的判决问题 如何判定整系数多项式是否有整数根如何判定整系数多项式是否有整数根?要求使用要求使用“有限次运算的过程有限次运算的过

5、程”自由停机问题 存在某种完全自动地回答一般问题（停机问题）的算法步骤吗？通过证明不存在决定图灵机停机问题的算法来证明不存在判定所有数学问题是否可解的问题。1970 年证明不存在这样的判定算法,即这个问题是不可判定的,或不可计算的.本讲稿第九页，共四十四页2.2.1图灵机概念图灵把人在计算时所作的工作分解成简单的动作。机器计算需要：(1)存储器（存储计算结果）(2)一种语言（表示运算和数字）(3)扫描(4)计算意向（计算过程中知道下一步做什么）(5)执行下一步计算本讲稿第十页，共四十四页一步计算；(1)改变数字和符号(2)扫描区改变(3)改变计算意向（采用二进制）本讲稿第十一页，共四十四页图灵

6、提出的图灵机具有以下两个性质：-具有有穷描述 -过程必须是由离散的、可机械执行的步骤组成一个移动将完成以下三个动作：-改变有穷控制器的状态 -在当前所读符号所在的带方格中印刷一个符号 -将读写头向右或者向左移一格本讲稿第十二页，共四十四页图灵机的直观描述3个部件：-有限状态控制器（有限状态机）-无穷多个带方格的输入带（符号集合）-读写头（读、改写、左移、右移）3个动作：改写当前格、左移或右移一格图灵机的计算：由控制器控制执行的一系列动作本讲稿第十三页，共四十四页仪器具有有限（虽然也许非常大的）数目的不同可能态的分立集合，把这些分立的集合称作仪器的内态内态。由于该仪器只有有限数目的不同的内态，不

7、能指望它把所有外部数据和所有自己计算的结果“内化”。相反地，它必须只考察那些立即立即处理的数据部分或者早先的计算，然后进行需要对它们进行的任何运算。正是输入、计算空间和输出的无限性质告诉我们，我们正在考虑的仅仅是一种数学的理想化，而不是在实际上可真正建造的某种东西。本讲稿第二十四页，共四十四页图灵是按照在上面作记号的“磁带”来描述其外部数据和存储空间的。一旦需要，仪器就会读取该磁带，并作为其运算的一部分，磁带可前后移动。仪器可把记号放到需要的地方，可抹去旧的记号。只要必须进行进一步的计算，该磁带就会穿过该仪器而不断地前后移动。当计算被最后完成时，仪器就停止，而计算的答案会在停于仪器一边的磁带的

8、部分上显示出来。为了确定起见，我们假定，答案总是在左边显示，而输入的所有数据以及要解的问题的详细说明总是由右边进去。本讲稿第二十五页，共四十四页在图灵的描述中，“磁带”是由方格的线性序列所组成，该序列在两个方向上都是无限的。在磁带的每一方格中或者是空白的或者包含有一个单独的记号。我们可利用有记号或者没有记号的方格来解释，我们的环境（也就是磁带）可允许被细分并按照分立分立（和连续相反的）元素来描述。如果希望仪器以一种可靠并绝对确定的方式工作。但是，在任何特殊的特殊的情形下，输入、计算和输出必须总是有限的有限的。这样，虽然可以取无限长的磁带，但是在它上面只应该有有限数目的实在的记号。磁带在每一个方

9、向的一定点以外必须是空白的。本讲稿第二十六页，共四十四页我们用符号“0”来表示空白方格，用符号“1”来代表记号方格 该仪器的内态内态在数目上是有限的。除了这种有限性之外，我们所需要知道的一切是该仪器的行为完全被其内态和输入所确定。我们已把输入简化成只是两个符号“0”或“1”之中的一个。仪器的初态和这一输入一给定，它就完全确定地运行；它把自己的内态改变成某种其他（或可能是同样的）内态，它用同样的或不同的符号0或1来取代它刚读过的0或1；它向右或向左移动一个方格；最后它决定是继续还是终止计算并停机。本讲稿第二十七页，共四十四页图灵机规则规则 如果 A 那么 B，形式化表示：A B 控制器当前状态读

10、写头当前位置的符号 图灵机控制器的规则：读写头移动动作指示读写头新位置的符号控制器新状态本讲稿第二十八页，共四十四页首先用标号0，1，2，3，4，5来为不同的内态编号；那么，用一张代换表可以完全指定该仪器或图图灵机灵机的运行过程 本讲稿第二十九页，共四十四页对上面图灵机的内态使用这种二进位记号，则原先的指令表便写成 本讲稿第三十页，共四十四页在假定我们的仪器处于由二进位序列1010010代表的特殊内态中，它处于计算的过程中，第36页给出了它的磁带，而且我们利用指令1101001011L 在磁带上被读的特殊位数（这里是位数“”）由一个更大写的数字指示，符号串的左边表示内态。读到的“”会被“1”所

11、取代，而内态变成11，然后仪器向左移动一格：本讲稿第三十一页，共四十四页【举例】图灵机UN+1：00R，01R，10STOP，10R。它简单地把一加到一个一进位数上。为了检查UN+1刚好做到这点，让我们想象，譬如讲把它应用到代表数4的磁带上去：。本讲稿第三十二页，共四十四页图灵机的意义图灵机的意义1）通用计算模型）通用计算模型：人们相信图灵机是一种通用的计算模型通用的计算模型，即任何人们能够想得到的算法都可以用图灵机实现。这个信念被称为丘奇丘奇-图灵论题图灵论题（Church-Turing Thesis）。这一信念有两个有力的证据：（1）其他学者提出的计算模型都被证明或者与图灵机在计算能力上是

12、等价的，或者不超过图灵机；（2）目前还没有发现一个算法不能用图灵机实现的。图灵机图灵机C语言程序语言程序 计算机计算机本讲稿第三十三页，共四十四页与电脑的机器指令的功能相比较，图灵机指令的功能是很简单的，仅有改变控制器的状态，让读写头改写一个字符，让读写头左移或右移一步等四种功能。但用图灵机可以实现电脑所做一切工作。但是作为理论模型，图灵机的存储设备，即输入带，是没有长度限制；而电脑的内存总是有限的。本讲稿第三十四页，共四十四页2）图灵机简单而强大，便于理论研究）图灵机简单而强大，便于理论研究图灵机的操作简单，指令形式简单，但功能强大，是一种简单的通用算法语言，便于用于研究算法与计算的一般规律

13、。因此，可以把图灵机作为“算法”的一个数学定义。这样，希尔伯特判定问题希尔伯特判定问题变成一个语义明确的“数学命题”：是否存在一个图灵机，能判定一个算术命题是否为真。本讲稿第三十五页，共四十四页3）可计算性理论可计算性理论：它是一种比较简单的计算模型，便于进行理论研究。以图灵、丘奇、克林等人的研究成果为基础与核心形成了一个新的数学理论，过去称为“递归论”，现在称为“可计算性理论”。它专门研究各种计算模型的计算能力之间的关系，论证具体的计算问题的可计算性。成为人们研究算法、程序和计算机的理论基础。在此基础上，又发展出了计算复杂性理论计算复杂性理论，研究算法运行的时间与空间效率，据此定义计算问题的

14、计算难度，目前研究的核心问题是：确定一些常见问题的计算难度；难解问题为什么是难解的。形式语言理论、可计算性理论和计算复杂性理论构成的理论计算机科学的基础与核心。本讲稿第三十六页，共四十四页与人的大脑比较：与人的大脑比较：人有10亿脑细胞，每个脑细胞的计算功能很简单，可以用一个简单的图灵机来模拟，10亿个简单图灵机组合成一个复杂系统，仍然是一个图灵机。强人工智能观点：人所能的都是图灵机所能的，反之亦强人工智能观点：人所能的都是图灵机所能的，反之亦然。然。包括：计算、推理、想象、创造、感知、形成观念、结成组织和社会、形成价值观、产生情感。因此，图灵机也是人力所能与所不能的区分标准。本讲稿第三十七页

15、，共四十四页通用图灵机图灵机本质在进行字符串的处理 图灵机输入是一个字符串 图灵机输出也是一个字符串如果将图灵机的有限内部状态与读写头的有限动作用字符串表示那么每条转换规则也可以用一个字符串表示（当前状态，当前符号，动作，新状态）图灵机可以由一个较长字符串完全表示 通用图灵机本讲稿第三十八页，共四十四页通用图灵机实现计算的过程发现什么？计算过程与具体的编码和规则都不相关！意味着什么？程序可以重复执行本讲稿第三十九页，共四十四页通用图灵机蕴含的计算思想（1）程序也是数据“x+1”图灵机功能是固定的，相当于一个程序通用的图灵机功能根据输入编码的不同而变化存储程序和程序控制M图灵机进一步展示了程序和

16、其输入可以先保存到存储带上，M就按程序一步一步运行直到给出结果，结果也保存在存储带上。本讲稿第四十页，共四十四页通用图灵机蕴含的计算思想（2）通用图灵机模型是计算机的计算能力的极限 因为，根据丘奇-图灵论题：不能用图灵机完成的计算任务是不可计算的计算机系统应该有:存储器（相当于存储带）中央处理器（控制器及其状态），并且其字母表可以仅有0和1两个符号；为了能将数据保存到存储器并将计算结果从存储器送出来展示给用户，计算机系统还应该有输入设备和输出设备如键盘、鼠标、显示器和打印机等。本讲稿第四十一页，共四十四页通用图灵机蕴含的计算思想（3）通用图灵机的所有规则构成指令集指示指示了操作的对象（当前符号

17、）指令指示了待实施的操作本讲稿第四十二页，共四十四页冯诺依曼机对图灵机的实现1944年，冯诺依曼参与ENIAC研究小组1945年,在ENIAC基础上，冯诺依曼提出了EDVAC（Electronic Discrete Variable AutomaticCompUter)设计方案,计算机的组成包括：运算器、逻辑控制装置、存储器、输入和输出设备本讲稿第四十三页，共四十四页新的概念的提出随机读写(Random Access)随机读写存储器RAM(Random Access Memory)地址(Address)指令(Instruction)=操作码(Operating Code,Opcode)+操作数(Operand)计算机指令系统精简指令集计算机复杂指令集计算机本讲稿第四十四页，共四十四页