1.图灵机与计算问题(1节课)

《1.图灵机与计算问题(1节课)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、图灵机的今生来世目录•1、问题的起源•2、图灵的贡献•3、图灵机•4、图灵机的计算极限与计算复杂性目录•1、问题的起源•2、图灵的贡献•3、图灵机•4、图灵机的计算极限与计算复杂性1、问题起源：费马大定理•17世纪，费马在阅读丢番图（Diophatus）《算术》拉丁文译本时，曾在第11卷第8命题旁写道：“将一个立方数分成两个立方数之和，或一个四次幂分成两个四次幂之和，或者一般地将一个高于二次的幂分成两个同次幂之和，这是不可能的。关于此，我确信已发现了一种美妙的证法，可惜这里空白的地方太小，写不下。”•当整数n>2时，关于x,y,z的方程xn+

2、yn=zn没有正整数解•1995年被英国数学家安德鲁·怀尔斯证明•1900年，著名的大数学家希尔伯特在第2届数学家大会上提出了著名的23个数学问题。•第十个问题（费马大定理的简化版）–存在不存在一种有限的、机械的步骤能够判断“丢番图方程”是否存在整数解？axb1+axb2+…+axbn=c,abc都是整数1122nni,i,丢番图（Diophantine）方程•对于丢番图方程，数学家们最感兴趣的是它是否有整数解（或自然数解）。–对于简单的方程这是很容易找到答案的•比如x2＋y2＝z2有整数解（勾三股四弦五）；2x－2y＝1则没有整数解（因为方

3、程的左边为偶数，右边却为奇数）•问题的实质–有限的、机械的证明步骤算法–注意：不是一般的证明步骤答案是：不存在！！•但在当时，人们还不知道“算法”是什么。实际上，当时数学领域中已经有很多问题都是跟“算法”密切相关的，因而，需要对“算法”进行科学的定义。•到了30年代的时候，终于有两个人分别提出了精确定义算法的方法，一个人是图灵，一个人是丘奇。而其中图灵提出来的图灵机模型直观形象，于是很快得到了大家的普遍接受。2、图灵的贡献•研究的课题是什么样的运算可以用机器来实现•1936年，图灵机为算法建立了模型，从而揭示了计算的本质•“论可计算数及其在

4、判定问题中的应用”(OnComputableNumbersWithanApplicationtotheEntscheidungsProblem)•在这个模型下，才有了计算理论，诱发了冯·诺依曼计算机的发明•人工智能的衡量标准“图灵测试”•人们称图灵为：计算机理论之父•阿兰·图灵(1912-1954)•8岁时，他写了他的第一篇“科学”短文，题目叫《说说显微镜》，头尾都是“你首先要知道，光线是直的”•二战，布雷契莱庄园，COLOSSUS•1950年，“机器能思考吗”的论文，成为划时代之作。“人工智能之父”•1954年6月8日，被发现死于家中的床上

5、，床头还放着一个被咬了一口的苹果。•1966年，ACM设立图灵奖图灵机的意义•图灵本意是想解决停机问题，但必须要定义好什么是“计算”才能解决这个问题，“捎带”提出了图灵机模型。•丢番图判定问题也得到了解决•图灵机的产生奠定了现代数字计算机的基础（后来冯诺依曼就是根据图灵的设想才设计出第一台计算机的）。•根据图灵机的概念，我们还可以看到可计算的极限是什么。也就是说实际上计算机的本领从原则上讲是有限制的（计算机也仍然存在着极限，这就是图灵机的停机问题）。3、图灵机一个图灵机是形如下面的一个装置：图灵机的组成•装置组成：–一个无限长的纸带（符号集合

6、）–一个读写头（读、改写、左移、右移）–内部状态（有限状态机）–还有一个程序对这个盒子进行控制。这个装置就是根据程序的命令以及它的内部状态进行磁带的读写、移动。图灵机的工作过程•工作过程：–从读写头在纸带上读出一个方格的信息–根据它当前的内部状态开始对程序进行查表，得出一个输出动作（是否往纸带上写信息，还是移动读写头到下一个方格）。–程序也会告诉它下一时刻内部状态转移到哪一个。•实质：根据每一时刻读写头读到的信息和当前的内部状态就可以确定它下一时刻的内部状态和输出动作了。有限状态机（FSM）当前状态输入信息输出动作下一状态B1前移CA0往纸带

7、上写1BC0后移A…..……四大要素:输入、输出、内部状态、程序如何理解图灵机？•1.小虫的比喻•2.如何理解图灵机模型1、小虫的比喻•怎样为小虫的信息处理过程建立图灵机模型•建模–小虫所处的世界是一个无限长的纸带，这个纸带上被分成了若干小的方格，而每个方格都仅仅只有黑和白两种颜色。–小虫仅能够感受到它所处的方格的颜色---输入信息。–小虫的输出动作就是往纸带上前爬一个方格或者后退一个方格。输入输出黑色前移•程序:NaiveBug白色后移小虫读到这个片断会怎样行动呢？•它先读到黑色，然后根据程序前移一个方格•由于目前仍为一个黑色信息，这个时候

8、它会根据程序再次前移一个方格，•仍然是黑色，再前移，•这个时候就读到白色方格了，根据程序它应该后退一个格，这个时候输入就是黑色了，•前移，白色，后移……，可以预见小