程序算法与图灵机模型

《程序算法与图灵机模型》由会员分享，可在线阅读，更多相关《程序算法与图灵机模型（34页珍藏版）》请在金锄头文库上搜索。

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 给出余数924 1365924 给出余数441 924441 给出余数42 44142 给出余数21 4221 给出余数0。 因此，用于做除数的21即是所需要的最大公 约数。,欧几里德算法逻辑运算的流程图,连续减法找到除法余数的流程图,图灵“机” 是一段“抽象数学”，是一种抽象计算模型

3、（通用计算模型）而不是一个物理对象。 用来精确定义可计算函数部分可计算函数与可计算函数 。 其目的是为了解决称为判决问题的一个范围广阔的问题。 通过研究图灵机，来研究递归可枚举集（recursively enumerable）和部分递归函数（partial recursive function） 对算法和可计算性进行研究提供形式化描述工具。,2.2 图灵机模型,图灵机缘起,1900,德国数学家希尔伯特(D. Hilbert )在巴黎第二届数学家大会上提出“23个数学难题“中, 逻辑的完备性问题,即是否所有数学问题原则上都可解. 1936, 英国数学家图灵 “论可计算数及其在判定问题中的应用”(

4、On Computable Numbers With an Application to the Entscheidungs Problem) 结论： 可解的问题是能够用“图灵机“的自动机理论模型表达的问题.,希尔伯特第十问题 数学问题的一般算法步骤问题（原则上是否存在一般数学问题的解题步骤的判决问题 如何判定整系数多项式是否有整数根? 要求使用 “有限次运算的过程” 自由停机问题 存在某种完全自动地回答一般问题（停机问题）的算法步骤吗？ 通过证明不存在决定图灵机停机问题的算法来证明不存在判定所有数学问题是否可解的问题。 1970 年证明不存在这样的判定算法, 即这个问题是 不可判定的, 或不

5、可计算的.,2.2.1图灵机概念,图灵把人在计算时所作的工作分解成简单的动作。 机器计算需要： (1) 存储器（存储计算结果） (2) 一种语言（表示运算和数字） (3) 扫描 (4) 计算意向（计算过程中知道下一步做什么） (5) 执行下一步计算,一步计算； (1) 改变数字和符号 (2) 扫描区改变 (3) 改变计算意向 （采用二进制）,图灵提出的图灵机具有以下两个性质： -具有有穷描述 -过程必须是由离散的、可机械执行的步骤组成 一个移动将完成以下三个动作： -改变有穷控制器的状态 -在当前所读符号所在的带方格中印刷一个符号 -将读写头向右或者向左移一格,图灵机的直观描述,3个部件： -

6、有限状态控制器（有限状态机） -无穷多个带方格的输入带（符号集合） -读写头（读、改写、左移、右移）,3个动作：改写当前格、左移或右移一格 图灵机的计算：由控制器控制执行的一系列动作,希尔伯特演讲(数学的哲学),1900 年夏天，第二届国际数学大会在巴黎 举行。大卫 希尔伯特(1862 1943)，著名 的德国数学家，哥廷根大学教授，应邀在大 会上作主要的演讲。希尔伯特提出了在21世 纪将被研究的 23 个主要的数学问题。图灵关 心的是其中希尔伯特第十问题（“ 判定丢番图 方程的可解性 ”判决问题 ）。 该问题超越出任何按照公理系统的特殊的数 学形式。问题在于，是否存在能在原则上一个 接一个地

7、解决所有（属于某种适当定义的族的 ）数学问题的某种一般的机械步骤？,希尔伯特第十问题（1）,数学家丢番图 主要著作称为算术，这一基础数学宝库共有 13 卷，成为代数理论和数论发展中的里程碑。 丢番图方程 “ 整数域上的代数方程 ” 定义为， P =0 ，其中 P 是 系统为整数的多项式，包含一个，两个或多个未知 数。例如 7x 2 - 5xy - 3y 2 + 2x + 4y - 11 = 0 和 x 3 + y 3 = z 3 。需要解决的问题是：给定方程 P (x , y , .) = 0 ，如何判定方程在整数域内是否有解，如 果有，如何高效找到所有解？,判定丢番图方程的可解性 给定一个系

8、数均为有理整数，包含任意个未知数的丢番图方程：设计一个过程，通过有限次的计算，能够判定该方程在有理数整数上是否可解。 如果某个问题包含无限种情况，则称为大量问题 （判定 n 是否为素数这一问题就是大量问题 ，需要对 n 值的无限集中的每个值进行判定 ）,希尔伯特第十问题（2）,另外一种不可解的 “ 大量问题 ” 在形式化理论上称为所谓的判定问题 。即此问题包含个数无限的个体问题，每个都要求明确的回答：是或否。 判定性问题的本质是要求寻找一个方法，使它对于所有的个体子问题都有明确的答案。,希尔伯特第十问题（3）,自丢番图提出著名的 “ 丢番图方程 ” 之后，很多通过数论方法得以解决，还有很多被证

9、明是不可解的。但是由于解决不同种类的方程和不同的个体方程，需要发明不同的，具体的方法。在第十问题中，希尔伯特要求一种通用方法来判定所有丢番图方程的可解性。 1936 年，图灵（研究的课题是什么样的运算可以用机器来实现 ）波斯特和丘奇提出了第一个关于算法的形式化概念。显而易见，同时他们发现首个不可解的大量问题 1950 年，马丁 戴维斯 在他的博士论文中向证明希尔伯特第十问题具有否定答案，即丢番图方程的不可解迈出了第一步。 该问题在1970年被俄国数学家马蒂亚塞维奇解决了。,希尔伯特第十问题（4）,“ 想法如下：一般计算科学表示信息的工具使用单词而非数字。然而，使用数字来表示单词的方法有多种。其

10、中有一种很自然地与丢番图方程关联。即不难证明任何 2 2 矩阵 其中 mij 为非负整数，并且行列式值为 1 ，可以唯一地表示为下面两种矩阵之积,希尔伯特第十问题（5）,可以证明任意个数的此类矩阵之积是一个矩阵，它的每个元素均为非负整数，并且它的行列式值为 1 。这意味着我们可以使用四元组 (m11 , m12 , m21 , m22 ) 唯一表示只含两个字母的字母表中的单词 ，如下： 显然数值 m11 , m12 , m21 , m22 满足丢番图方程 m 11 m 22 - m 21 m 12 = 1.,希尔伯特第十问题（6）,依照这种使用矩阵表示单词的方法，单词间的串接运算对应矩阵的乘法

11、运算，因此很容易将单词运算表示为丢番图方程系。这为把任意单词方程系转换成等价的丢番图方程开辟一种新方法。许多关于单词的判定问题已被证明为不可判定问题，因此很自然通过证明单词方程系的不可判定性来设法攀登希尔伯特第十问题。 ” 我们可以从下面得到结论：马蒂亚塞维奇的主要方法是通过证明单词方程系的不可判定性来演绎推导丢番图方程的不可判定性。,希尔伯特第十问题（7）,使用斐波纳契数来解决希尔伯特第十问题的。马蒂亚塞维奇写道： 下一步是考虑一类带有谓词的更广的单词方程。由于最终目标终始是希尔伯特第十问题，所以我仅考虑那些可以表示（或经过一定编码后可以表示）为丢番图方程的谓词。依照这一方法，我想到那些关于

12、单词和长度的方程，可以通过使用著名斐波纳契数来简化。众所周知，任何自然均可唯一地表示为任意不同的和不连续的斐波纳契数之和。因此，我们可以把自然数看成为只有两个字符 0 ， 1 的字母表中的单词，其中有一限制就是字母表中的单词不能有两个相连的 1 注 。我可以证明，按照此方法使用字数表示单词，那么单词的串接运算，以及单词间的长度关系式均可表示为丢番图方程 ” 。,希尔伯特第十问题（8）,任何自然数均表示为任意不同的不连续的斐波纳契数之和，例如 30 可以表示为 30=21 + 8 + 1=21x11 +13x10 +8x11 +5x10 +3x10 +2x10 +1x11 。因此数字 30 对应

13、的单词是 “1010001” 。由于表达中不存在连续的斐波纳契数，故对应的单中不存在连续的两个 “1” 。,希尔伯特第十问题（9）,仪器具有有限（虽然也许非常大的）数目的不同可能态的分立集合，把这些分立的集合称作仪器的内态。 由于该仪器只有有限数目的不同的内态，不能指望它把所有外部数据和所有自己计算的结果“内化”。相反地，它必须只考察那些立即处理的数据部分或者早先的计算，然后进行需要对它们进行的任何运算。 正是输入、计算空间和输出的无限性质告诉我们，我们正在考虑的仅仅是一种数学的理想化，而不是在实际上可真正建造的某种东西。,图灵是按照在上面作记号的“磁带”来描述其外部数据和存储空间的。一旦需要

14、，仪器就会读取该磁带，并作为其运算的一部分，磁带可前后移动。仪器可把记号放到需要的地方，可抹去旧的记号。 只要必须进行进一步的计算，该磁带就会穿过该仪器而不断地前后移动。当计算被最后完成时，仪器就停止，而计算的答案会在停于仪器一边的磁带的部分上显示出来。为了确定起见，我们假定，答案总是在左边显示，而输入的所有数据以及要解的问题的详细说明总是由右边进去。,在图灵的描述中，“磁带”是由方格的线性序列所组成，该序列在两个方向上都是无限的。在磁带的每一方格中或者是空白的或者包含有一个单独的记号。我们可利用有记号或者没有记号的方格来解释，我们的环境（也就是磁带）可允许被细分并按照分立（和连续相反的）元素

15、来描述。如果希望仪器以一种可靠并绝对确定的方式工作。 但是，在任何特殊的情形下，输入、计算和输出必须总是有限的。这样，虽然可以取无限长的磁带，但是在它上面只应该有有限数目的实在的记号。磁带在每一个方向的一定点以外必须是空白的。,我们用符号“0”来表示空白方格，用符号“1”来代表记号方格 该仪器的内态在数目上是有限的。除了这种有限性之外，我们所需要知道的一切是该仪器的行为完全被其内态和输入所确定。我们已把输入简化成只是两个符号“0”或“1”之中的一个。仪器的初态和这一输入一给定，它就完全确定地运行；它把自己的内态改变成某种其他（或可能是同样的）内态，它用同样的或不同的符号0或1来取代它刚读过的0

16、或1；它向右或向左移动一个方格；最后它决定是继续还是终止计算并停机。,图灵机规则,规则 如果 A 那么 B，形式化表示：A B,控制器当前状态 读写头当前位置的符号,图灵机控制器的规则：,读写头移动动作指示 读写头新位置的符号 控制器新状态,首先用标号0，1，2，3，4，5来为不同的内态编号；那么，用一张代换表可以完全指定该仪器或图灵机的运行过程,对上面图灵机的内态使用这种二进位记号，则原先的指令表便写成,在假定我们的仪器处于由二进位序列1010010代表的特殊内态中，它处于计算的过程中，第36页给出了它的磁带，而且我们利用指令1101001011L 在磁带上被读的特殊位数（这里是位数“”）由一个更大写的数字指示，符号串的左边表示内态。读到的“”会被“1”所取代，而内态变成11，然后仪器向左移动一格：,【举例】 图灵机UN+1： 00R， 01R， 10STOP， 10R。 它简单地把一加到一个一进位数上。为了检查UN+1刚好做到这点，让我们想象，譬如讲把它