程序算法与图灵机模型.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 给出余数924 1365924 给出余数441 924441 给出余数42 44142 给出余数21 4221 给出余数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 年证明不存在这样的判定算法, 即这个问题是 不可判定的, 或不可计算的. 2.2.1图灵机概念 图灵把人在计算时所作的工作分解成简单 的动作。 机器计算需要： (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页 给出了它的磁带，而且我们利用指令11010010 11L 在磁带上被读的特殊位数（这里是位数“”）由 一个更大写的数字指示，符号串的左边表示内态 。读到的“”会被“1”所取代，而内态变成11， 然后仪器向左移动一格： 【举例】 图灵机UN+1： 00R， 01R， 10STOP， 10R。 它简单地把一加到一个一进位数上。为了检 查UN+1刚好做到这点，让我们想象，譬如 讲把它应用到代表数4的磁带上去： 。 图灵机的意义 1）通用计算模型： 人们相信图灵机是一种通用的计算模型， 即任何 人们能够想得到的算法都可以用图灵机实现。这 个信念被称为丘奇-图灵论题（Church-Turing Thesis）。 这一信念有两个有力的证据： （1）其他学者提出的计算模型都被证明或者与 图灵机在计算能力上是等价的，或者不超过图灵 机； （2）目前还没有发现一个算法不能用图灵机实 现的。 图灵机C语言程序 计算机 与电脑的机器指令的功能相比较，图灵机 指令的功能是很简单的，仅有改变控制器 的状态，让读写头改写一个字符，让读写 头左移或右移一步等四种功能。但用图灵 机可以实现电脑所做一切工作。但是作为 理论模型，图灵机的存储设备，即输入带 ，是没有长度限制；而电脑的内存总是有 限的。 2）图灵机简单而强大，便于理论研究 图灵机的操作简单，指令形式简单，但功 能强大，是一种简单的通用算法语言，便 于用于研究算法与计算的一般规律。因此 ，可以把图灵机作为“算法”的一个数学定义 。 这样，希尔伯特判定问题变成一个语义明 确的“数学命题”：是否存在一个图灵机，能 判定一个算术命题是否为真。 3）可计算性理论： 它是一种比较简单的计算模型，便于进行理论研究。以图 灵、丘奇、克林等人的研究成果为基础与核心形成了一个 新的数学理论，过去称为“递归论”，现在称为“可计算性理 论”。它专门研究各种计算模型的计算能力之间的关系， 论证具体的计算问题的可计算性。成为人们研究算法、程 序和计算机的理论基础。在此基础上，又发展出了计算复 杂性理论，研究算法运行的时间与空间效率，据此定义计 算问题的计算难度，目前研究的核心问题是：确定一些常 见问题的计算难度；难解问题为什么是难解的。形式语言 理论、可计算性理论和计算复杂性理论构成的理论计算机 科学的基础与核心。 与人的大脑比较： 人有10亿脑细胞，每个脑细胞的计算功能很简单 ，可以用一个简单的图灵机来模拟，10亿个简单 图灵机组合成一个复杂系统，仍然是一个图灵机 。 强人工智能观点：人所能的都是图灵机所能的， 反之亦然。 包括：计算、推理、想象、创造、感知、形成观 念、结成组织和社会、形成价值观、产生情感。 因此，图灵机也是人力所能与所不能的区分标准 。 通用图灵机 图灵机本质在进行字符串的处理 图灵机输入是一个字符串 图灵机输出也是一个字符串 如果将图灵机的有限内部状态与读写头的 有限动作用字符串表示 那么每条转换规则也可以用一个字符串表 示（当前状态，当前符号，动作，新状态 ） 图灵机可以由一个较长字符串完全表示 通用图灵机 通用图灵机实现计算的过程 发现什么？ 计算过程与具体的编 码和规则都不相关！ 意味着什么？ 程序可以重复执行 通用图灵机蕴含的计算思想（1