程序算法与图灵机模型

《程序算法与图灵机模型》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、总是小数往前放，大数往后放，相当于气泡往上升)二分法之求函数的解(对于函数f(x),如果存在实数c,当x=c时，若f(c)=0,那么把x=c叫做函数f(x)的零点。解方程即要求f(x)的所有零点。)1365和3654两数的最大公约数？步骤：3654÷1365给出余数9241365÷924给出余数441924÷441给出余数42441÷42给出余数2142÷21给出余数0。因此，用于做除数的21即是所需要的最大公约数。欧几里德算法逻辑运算的流程图连续减法找到除法余数的流程图图灵“机”是一段“抽象数学”，是一种抽象计算模型（通用计算模型）而不是一个物理对象。用来精确定义可计算函数——部分可计算函数

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

4、Problem)结论：可解的问题是能够用"图灵机"的自动机理论模型表达的问题.希尔伯特第十问题——数学问题的一般算法步骤问题（原则上是否存在一般数学问题的解题步骤的判决问题如何判定整系数多项式是否有整数根?要求使用“有限次运算的过程”自由停机问题存在某种完全自动地回答一般问题（停机问题）的算法步骤吗？通过证明不存在决定图灵机停机问题的算法来证明不存在判定所有数学问题是否可解的问题。1970年证明不存在这样的判定算法,即这个问题是不可判定的,或不可计算的.2.2.1图灵机概念图灵把人在计算时所作的工作分解成简单的动作。机器计算需要：(1)存储器（存储计算结果）(2)一种语言（表示运算和数字）(3

5、)扫描(4)计算意向（计算过程中知道下一步做什么）(5)执行下一步计算一步计算；(1)改变数字和符号(2)扫描区改变(3)改变计算意向（采用二进制）图灵提出的图灵机具有以下两个性质：-具有有穷描述-过程必须是由离散的、可机械执行的步骤组成一个移动将完成以下三个动作：-改变有穷控制器的状态-在当前所读符号所在的带方格中印刷一个符号-将读写头向右或者向左移一格图灵机的直观描述3个部件：-有限状态控制器（有限状态机）-无穷多个带方格的输入带（符号集合）-读写头（读、改写、左移、右移）3个动作：改写当前格、左移或右移一格图灵机的计算：由控制器控制执行的一系列动作希尔伯特演讲(数学的哲学)1900年夏天

6、，第二届国际数学大会在巴黎举行。大卫·希尔伯特(1862－1943)，著名的德国数学家，哥廷根大学教授，应邀在大会上作主要的演讲。希尔伯特提出了在21世纪将被研究的23个主要的数学问题。图灵关心的是其中希尔伯特第十问题（“判定丢番图方程的可解性”判决问题）。该问题超越出任何按照公理系统的特殊的数学形式。问题在于，是否存在能在原则上一个接一个地解决所有（属于某种适当定义的族的）数学问题的某种一般的机械步骤？希尔伯特第十问题（1）☆数学家丢番图主要著作称为《算术》，这一基础数学宝库共有13卷，成为代数理论和数论发展中的里程碑。☆丢番图方程“整数域上的代数方程”定义为，P=0，其中P是系统为整数的多

7、项式，包含一个，两个或多个未知数。例如7x2-5xy-3y2+2x+4y-11=0和x3+y3=z3。需要解决的问题是：给定方程P(x,y,...)=0，如何判定方程在整数域内是否有解，如果有，如何高效找到所有解？判定丢番图方程的可解性给定一个系数均为有理整数，包含任意个未知数的丢番图方程：设计一个过程，通过有限次的计算，能够判定该方程在有理数整数上是否可解。如果某个问题包含无限种情况，则称为大量