程序算法与图灵机模型.ppt

第2章 程序算法与图灵机模型,2.1 算法,什么是算法？指完成一个任务所需要的具体步骤和方法。即给定初始状态或输入数据，经过计算机程序的有限次运算，能够得出所要求或期望的终止状态或输出数据。,算法的特点：,(1)有穷性 算法中每一条指令的执行次数有限，执行每条指令的时间有限。(对任何的合法输入，算法总能在运算有限步后终止)(2)确定性 组成算法的每条指令是清晰的，无歧义的。(3)输入 一个算法有零个或多个输入。(4)输出 一个算法至少产生一个量作为输出。(5)可行性 算法中的运算是能够实现的基本运算，每一种运算可在有限的时间内完成。,一些经典的算法,思考：求两个数的最大公约数如何实现？P27排序之冒泡排序(在排序过程中总是小数往前放，大数往后放，相当于气泡往上升)二分法之求函数的解(对于函数f(x),如果存在实数c,当x=c时，若f(c)=0,那么把x=c叫做函数f(x)的零点。解方程即要求f(x)的所有零点。),1365和3654 两数的最大公约数？步骤：36541365 给出余数9241365924 给出余数441924441 给出余数4244142 给出余数214221 给出余数0。因此，用于做除数的21即是所需要的最大公约数。,欧几里德算法逻辑运算的流程图,连续减法找到除法余数的流程图,图灵“机”是一段“抽象数学”，是一种抽象计算模型（通用计算模型）而不是一个物理对象。用来精确定义可计算函数部分可计算函数与可计算函数。其目的是为了解决称为判决问题的一个范围广阔的问题。通过研究图灵机，来研究递归可枚举集（recursively enumerable）和部分递归函数（partial recursive function）对算法和可计算性进行研究提供形式化描述工具。,2.2 图灵机模型,图灵机缘起,1900,德国数学家希尔伯特(D.Hilbert)在巴黎第二届数学家大会上提出23个数学难题中,逻辑的完备性问题,即是否所有数学问题原则上都可解.1936,英国数学家图灵“论可计算数及其在判定问题中的应用”(On Computable Numbers With an Application to the Entscheidungs Problem)结论：可解的问题是能够用图灵机的自动机理论模型表达的问题.,希尔伯特第十问题数学问题的一般算法步骤问题（原则上是否存在一般数学问题的解题步骤的判决问题 如何判定整系数多项式是否有整数根?要求使用“有限次运算的过程”自由停机问题 存在某种完全自动地回答一般问题（停机问题）的算法步骤吗？通过证明不存在决定图灵机停机问题的算法来证明不存在判定所有数学问题是否可解的问题。1970 年证明不存在这样的判定算法,即这个问题是不可判定的,或不可计算的.,图灵机概念,图灵把人在计算时所作的工作分解成简单的动作。机器计算需要：(1)存储器（存储计算结果）(2)一种语言（表示运算和数字）(3)扫描(4)计算意向（计算过程中知道下一步做什么）(5)执行下一步计算,一步计算；(1)改变数字和符号(2)扫描区改变(3)改变计算意向（采用二进制）,图灵提出的图灵机具有以下两个性质：-具有有穷描述-过程必须是由离散的、可机械执行的步骤组成一个移动将完成以下三个动作：-改变有穷控制器的状态-在当前所读符号所在的带方格中印刷一个符号-将读写头向右或者向左移一格,图灵机的直观描述,3个部件：-有限状态控制器（有限状态机）-无穷多个带方格的输入带（符号集合）-读写头（读、改写、左移、右移）,3个动作：改写当前格、左移或右移一格图灵机的计算：由控制器控制执行的一系列动作,希尔伯特演讲(数学的哲学),1900 年夏天，第二届国际数学大会在巴黎举行。大卫 希尔伯特(1862 1943)，著名的德国数学家，哥廷根大学教授，应邀在大会上作主要的演讲。希尔伯特提出了在21世纪将被研究的 23 个主要的数学问题。图灵关心的是其中希尔伯特第十问题（“判定丢番图方程的可解性”判决问题）。该问题超越出任何按照公理系统的特殊的数学形式。问题在于，是否存在能在原则上一个接一个地解决所有（属于某种适当定义的族的）数学问题的某种一般的机械步骤？,希尔伯特第十问题（1）,数学家丢番图主要著作称为算术，这一基础数学宝库共有 13 卷，成为代数理论和数论发展中的里程碑。丢番图方程“整数域上的代数方程”定义为，P=0，其中 P 是系统为整数的多项式，包含一个，两个或多个未知数。例如 7x 2-5xy-3y 2+2x+4y-11=0 和 x 3+y 3=z 3。需要解决的问题是：给定方程 P(x,y,.)=0，如何判定方程在整数域内是否有解，如果有，如何高效找到所有解？,判定丢番图方程的可解性 给定一个系数均为有理整数，包含任意个未知数的丢番图方程：设计一个过程，通过有限次的计算，能够判定该方程在有理数整数上是否可解。如果某个问题包含无限种情况，则称为大量问题（判定 n 是否为素数这一问题就是大量问题，需要对 n 值的无限集中的每个值进行判定）,希尔伯特第十问题（2）,另外一种不可解的“大量问题”在形式化理论上称为所谓的判定问题。即此问题包含个数无限的个体问题，每个都要求明确的回答：是或否。判定性问题的本质是要求寻找一个方法，使它对于所有的个体子问题都有明确的答案。,希尔伯特第十问题（3）,自丢番图提出著名的“丢番图方程”之后，很多通过数论方法得以解决，还有很多被证明是不可解的。但是由于解决不同种类的方程和不同的个体方程，需要发明不同的，具体的方法。在第十问题中，希尔伯特要求一种通用方法来判定所有丢番图方程的可解性。1936 年，图灵（研究的课题是什么样的运算可以用机器来实现）波斯特和丘奇提出了第一个关于算法的形式化概念。显而易见，同时他们发现首个不可解的大量问题 1950 年，马丁 戴维斯 在他的博士论文中向证明希尔伯特第十问题具有否定答案，即丢番图方程的不可解迈出了第一步。该问题在1970年被俄国数学家马蒂亚塞维奇解决了。,希尔伯特第十问题（4）,“想法如下：一般计算科学表示信息的工具使用单词而非数字。然而，使用数字来表示单词的方法有多种。其中有一种很自然地与丢番图方程关联。即不难证明任何 2 2 矩阵 其中 mij 为非负整数，并且行列式值为 1，可以唯一地表示为下面两种矩阵之积,希尔伯特第十问题（5）,可以证明任意个数的此类矩阵之积是一个矩阵，它的每个元素均为非负整数，并且它的行列式值为 1。这意味着我们可以使用四元组(m11,m12,m21,m22)唯一表示只含两个字母的字母表中的单词，如下：显然数值 m11,m12,m21,m22 满足丢番图方程 m 11 m 22-m 21 m 12=1.,希尔伯特第十问题（6）,依照这种使用矩阵表示单词的方法，单词间的串接运算对应矩阵的乘法运算，因此很容易将单词运算表示为丢番图方程系。这为把任意单词方程系转换成等价的丢番图方程开辟一种新方法。许多关于单词的判定问题已被证明为不可判定问题，因此很自然通过证明单词方程系的不可判定性来设法攀登希尔伯特第十问题。”我们可以从下面得到结论：马蒂亚塞维奇的主要方法是通过证明单词方程系的不可判定性来演绎推导丢番图方程的不可判定性。,希尔伯特第十问题（7）,使用斐波纳契数来解决希尔伯特第十问题的。马蒂亚塞维奇写道：下一步是考虑一类带有谓词的更广的单词方程。由于最终目标终始是希尔伯特第十问题，所以我仅考虑那些可以表示（或经过一定编码后可以表示）为丢番图方程的谓词。依照这一方法，我想到那些关于单词和长度的方程，可以通过使用著名斐波纳契数来简化。众所周知，任何自然均可唯一地表示为任意不同的和不连续的斐波纳契数之和。因此，我们可以把自然数看成为只有两个字符 0，1 的字母表中的单词，其中有一限制就是字母表中的单词不能有两个相连的 1 注。我可以证明，按照此方法使用字数表示单词，那么单词的串接运算，以及单词间的长度关系式均可表示为丢番图方程”。,希尔伯特第十问题（8）,任何自然数均表示为任意不同的不连续的斐波纳契数之和，例如 30 可以表示为 30=21+8+1=21x11+13x10+8x11+5x10+3x10+2x10+1x11。因此数字 30 对应的单词是“1010001”。由于表达中不存在连续的斐波纳契数，故对应的单中不存在连续的两个“1”。,希尔伯特第十问题（9）,仪器具有有限（虽然也许非常大的）数目的不同可能态的分立集合，把这些分立的集合称作仪器的内态。由于该仪器只有有限数目的不同的内态，不能指望它把所有外部数据和所有自己计算的结果“内化”。相反地，它必须只考察那些立即处理的数据部分或者早先的计算，然后进行需要对它们进行的任何运算。正是输入、计算空间和输出的无限性质告诉我们，我们正在考虑的仅仅是一种数学的理想化，而不是在实际上可真正建造的某种东西。,图灵是按照在上面作记号的“磁带”来描述其外部数据和存储空间的。一旦需要，仪器就会读取该磁带，并作为其运算的一部分，磁带可前后移动。仪器可把记号放到需要的地方，可抹去旧的记号。只要必须进行进一步的计算，该磁带就会穿过该仪器而不断地前后移动。当计算被最后完成时，仪器就停止，而计算的答案会在停于仪器一边的磁带的部分上显示出来。为了确定起见，我们假定，答案总是在左边显示，而输入的所有数据以及要解的问题的详细说明总是由右边进去。,在图灵的描述中，“磁带”是由方格的线性序列所组成，该序列在两个方向上都是无限的。在磁带的每一方格中或者是空白的或者包含有一个单独的记号。我们可利用有记号或者没有记号的方格来解释，我们的环境（也就是磁带）可允许被细分并按照分立（和连续相反的）元素来描述。如果希望仪器以一种可靠并绝对确定的方式工作。但是，在任何特殊的情形下，输入、计算和输出必须总是有限的。这样，虽然可以取无限长的磁带，但是在它上面只应该有有限数目的实在的记号。磁带在每一个方向的一定点以外必须是空白的。,我们用符号“0”来表示空白方格，用符号“1”来代表记号方格 该仪器的内态在数目上是有限的。除了这种有限性之外，我们所需要知道的一切是该仪器的行为完全被其内态和输入所确定。我们已把输入简化成只是两个符号“0”或“1”之中的一个。仪器的初态和这一输入一给定，它就完全确定地运行；它把自己的内态改变成某种其他（或可能是同样的）内态，它用同样的或不同的符号0或1来取代它刚读过的0或1；它向右或向左移动一个方格；最后它决定是继续还是终止计算并停机。,图灵机规则,规则 如果 A 那么 B，形式化表示：A B,控制器当前状态读写头当前位置的符号,图灵机控制器的规则：,读写头移动动作指示读写头新位置的符号控制器新状态,首先用标号0，1，2，3，4，5来为不同的内态编号；那么，用一张代换表可以完全指定该仪器或图灵机的运行过程,对上面图灵机的内态使用这种二进位记号，则原先的指令表便写成,在假定我们的仪器处于由二进位序列1010010代表的特殊内态中，它处于计算的过程中，第36页给出了它的磁带，而且我们利用指令1101001011L 在磁带上被读的特殊位数（这里是位数“”）由一个更大写的数字指示，符号串的左边表示内态。读到的“”会被“1”所取代，而内态变成11，然后仪器向左移动一格：,【举例】图灵机UN+1：00R，01R，10STOP，10R。它简单地把一加到一个一进位数上。为了检查UN+1刚好做到这点，让我们想象，譬如讲把它应用到代表数4的磁带上去：。,图灵机的意义,1）通用计算模型：人们相信图灵机是一种通用的计算模型，即任何人们能够想得到的算法都可以用图灵机实现。这个信念被称为丘奇-图灵论题（Church-Turing Thesis）。这一信念有两个有力的证据：（1）其他学者提出的计算模型都被证明或者与图灵机在计算能力上是等价的，或者不超过图灵机；（2）目前还没有发现一个算法不能用图灵机实现的。图灵机C语言程序 计算机,与电脑的机器指令的功能相比较，图灵机指令的功能是很简单的，仅有改变控制器的状态，让读写头改写一个字符，让读写头左移或右移一步等四种功能。但用图灵机可以实现电脑所做一切工作。但是作为理论模型，图灵机的存储设备，即输入带，是没有长度限制；而电脑的内存总是有限的。,2）图灵机简单而强大，便于理论研究图灵机的操作简单，指令形式简单，但功能强大，是一种简单的通用算法语言，便于用于研究算法与计算的一般规律。因此，可以把图灵机作为“算法”的一个数学定义。这样，希尔伯特判定问题变成一个语义明确的“数学命题”：是否存在一个图灵机，能判定一个算术命题是否为真。,3）可计算性理论：它是一种比较简单的计算模型，便于进行理论研究。以图灵、丘奇、克林等人的研究成果为基础与核心形成了一个新的数学理论，过去称为“递归论”，现在称为“可计算性理论”。它专门研究各种计算模型的计算能力之间的关系，论证具体的计算问题的可计算性。成为人们研究算法、程序和计算机的理论基础。在此基础上，又发展出了计算复杂性理论，研究算法运行的时间与空间效率，据此定义计算问题的计算难度，目前研究的核心问题是：确定一些常见问题的计算难度；难解问题为什么是难解的。形式语言理论、可计算性理论和计算复杂性理论构成的理论计算机科学的基础与核心。,与人的大脑比较：人有10亿脑细胞，每个脑细胞的计算功能很简单，可以用一个简单的图灵机来模拟，10亿个简单图灵机组合成一个复杂系统，仍然是一个图灵机。强人工智能观点：人所能的都是图灵机所能的，反之亦然。包括：计算、推理、想象、创造、感知、形成观念、结成组织和社会、形成价值观、产生情感。因此，图灵机也是人力所能与所不能的区分标准。,通用图灵机,图灵机本质在进行字符串的处理 图灵机输入是一个字符串 图灵机输出也是一个字符串如果将图灵机的有限内部状态与读写头的有限动作用字符串表示那么每条转换规则也可以用一个字符串表示（当前状态，当前符号，动作，新状态）图灵机可以由一个较长字符串完全表示 通用图灵机,通用图灵机实现计算的过程,发现什么？,计算过程与具体的编码和规则都不相关！,意味着什么？,程序可以重复执行,通用图灵机蕴含的计算思想（1）,程序也是数据“x+1”图灵机功能是固定的，相当于一个程序通用的图灵机功能根据输入编码的不同而变化存储程序和程序控制M图灵机进一步展示了程序和其输入可以先保存到存储带上，M就按程序一步一步运行直到给出结果，结果也保存在存储带上。,通用图灵机蕴含的计算思想（2）,通用图灵机模型是计算机的计算能力的极限 因为，根据丘奇-图灵论题：不能用图灵机完成的计算任务是不可计算的计算机系统应该有:存储器（相当于存储带）中央处理器（控制器及其状态），并且其字母表可以仅有0和1两个符号；为了能将数据保存到存储器并将计算结果从存储器送出来展示给用户，计算机系统还应该有输入设备和输出设备如键盘、鼠标、显示器和打印机等。,通用图灵机蕴含的计算思想（3）,通用图灵机的所有规则构成指令集指示指示了操作的对象（当前符号）指令指示了待实施的操作,冯诺依曼机对图灵机的实现,1944年，冯诺依曼参与ENIAC研究小组1945年,在ENIAC基础上，冯诺依曼提出了EDVAC（Electronic Discrete Variable AutomaticCompUter)设计方案,计算机的组成包括：运算器、逻辑控制装置、存储器、输入和输出设备,新的概念的提出,随机读写(Random Access)随机读写存储器RAM(Random Access Memory)地址(Address)指令(Instruction)=操作码(Operating Code,Opcode)+操作数(Operand)计算机指令系统精简指令集计算机复杂指令集计算机,