《图灵机与计算问题(1节课时)》由会员分享，可在线阅读，更多相关《图灵机与计算问题(1节课时)（50页珍藏版）》请在金锄头文库上搜索。
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个数 学问题。 第十个问题（费马大定理的简化版） 存在不存在一种有限的、机械的步骤 能够判断“丢番图方程”是否存在整 数解？ a1x1b1+a2x2b2+anxnbn=c, ai,bi,c都是整数 丢番图（Diophantine）方程 对于丢番图方程，数学家们最感兴趣 的是它是否有整数解（或自然数解）。 对于简单的方程这是很容易找到答案的 比如x2y2z2有整数解（勾三股四弦五）； 2x2y1则没有整数解（因为方程的左边 为偶数，右边却为奇数） 问题的实
3、质 有限的、机械的证明步骤 算法 注意：不是一般的证明步骤 答案是：不存在！ 但在当时，人们还不知道“算法”是什 么。实际上，当时数学领域中已经有很 多问题都是跟“算法”密切相关的，因 而，需要对“算法”进行科学的定义。 到了30年代的时候，终于有两个人分别 提出了精确定义算法的方法，一个人是 图灵，一个人是丘奇。而其中图灵提出 来的图灵机模型直观形象，于是很快得 到了大家的普遍接受。 2、图灵的贡献 研究的课题是什么样的运算可以用机器来实现 1936年，图灵机为算法建立了模型，从而揭示了 计算的本质 “论可计算数及其在判定问题中的应用”(On Computable Numbers With
4、an Application to the Entscheidungs Problem) 在这个模型下，才有了计算理论，诱发了冯诺依 曼计算机的发明 人工智能的衡量标准“图灵测试” 人们称图灵为：计算机理论之父 阿兰图灵(1912-1954) 8岁时，他写了他的第一篇“科学”短文，题目叫说 说显微镜，头尾都是“你首先要知道，光线是直的” 二战 ，布雷契莱庄园，COLOSSUS 1950年，“机器能思考吗”的论文，成为划时 代之作。“人工智能之父” 1954年6月8日，被发现死于家中的床上，床头 还放着一个被咬了一口的苹果。 1966年，ACM设立 图灵奖 图灵机的意义 图灵本意是想解决停机问题
5、，但必须要定义好什么是“计算”才 能解决这个问题，“捎带”提出了图灵机模型。 丢番图判定问题也得到了解决 图灵机的产生奠定了现代数字计算机的基础（后来冯诺依曼就是 根据图灵的设想才设计出第一台计算机的）。 根据图灵机的概念，我们还可以看到可计算的极限是什么。也就 是说实际上计算机的本领从原则上讲是有限制的（计算机也仍然 存在着极限，这就是图灵机的停机问题）。 3、图灵机、图灵机 一个图灵机是形如下面的一个装置 ： 图灵机的组成 装置组成： 一个无限长的纸带（符号集合） 一个读写头（读、改写、左移、右移） 内部状态（有限状态机） 还有一个程序对这个盒子进行控制。这个装 置就是根据程序的命令以及它
6、的内部状态进 行磁带的读写、移动。 图灵机的工作过程 工作过程： 从读写头在纸带上读出一个方格的信息 根据它当前的内部状态开始对程序进行查表，得出一个 输出动作（是否往纸带上写信息，还是移动读写头到下 一个方格）。 程序也会告诉它下一时刻内部状态转移到哪一个。 实质： 根据每一时刻读写头读到的信息和当前的内部状态 就可以确定它下一时刻的内部状态和输出动作了。 有限状态机（FSM） 当前状态当前状态输入信息输入信息输出动作输出动作下一状态下一状态 B1前移C A0往纸带上写1B C0后移A . 四大要素: 输入、输出、内部状态、程序 如何理解图灵机？如何理解图灵机？ 1.小虫的比喻 2.如何理解
7、图灵机模型 1、小虫的比喻 怎样为小虫的信息处理过程建立图灵机模型 建模 小虫所处的世界是一个无限长的纸带，这个纸带上 被分成了若干小的方格，而每个方格都仅仅只有黑 和白两种颜色。 小虫仅能够感受到它所处的方格的颜色-输 入信息。 小虫的输出动作就是往纸带上前爬一个方格 或者后退一个方格。 程序: NaiveBug 输入输入输出输出 黑色前移 白色后移 小虫读到这个片断会怎样行动呢？ 它先读到黑色，然后根据程序前移一个方格 由于目前仍为一个黑色信息，这个时候它会根据程序 再次前移一个方格， 仍然是黑色，再前移， 这个时候就读到白色方格了，根据程序它应该后退一 个格，这个时候输入就是黑色了， 前
8、移，白色，后移，可以预见小虫会无限的循环 下去。 改进程序NaiveBug 现实世界中的小虫肯定不会这样傻的在那里无 限循环下去。 说明所建立的模型不能准确的描述事实。 如何改造？ 首先，我们知道小虫除了可以机械地在世界上移动 以外，还会对世界本身造成影响，因而改变这个世 界。比如虫子看到旁边有食物，它就会把那个东西 吃掉了。在我们这个模型中，也就相当于我们必须 假设小虫可以改写纸带上的信息。 小虫可能的输出动作集合就变成了：O=前移，后 移，涂黑。 程序GoodBug 输入输出 黑前移 白涂黑 . 输入输入输出输出 黑前移 白涂黑 改进程序BetterBug 固定的输入得到固定的输出，现实世
9、界中的小 虫肯定不会这样固定。 如何改造？ 加入小虫的内部状态。 假设黑色方格表示是食物，虫子可以吃掉它，而当 吃到一个食物后，小虫子就会感觉到饱了。当读入 的信息是白色方格的时候，虽然没有食物但它仍然 吃饱了，只有当再次读入黑色时候它才会感觉到自 己饥饿了。因而，我们说小虫具有两个内部状态， 并把它内部状态的集合记为：S=饥饿，吃饱。 这样小虫行为的时候就会不仅根据它的输入信息， 而且也会根据它当前的内部状态来决定它的输出动 作，并且还要更改它的内部状态 小虫会怎样行动呢？ 输入输入当前状态当前状态输出输出下一个状态下一个状态 黑饥饿涂白吃饱 黑吃饱后移饥饿 白饥饿涂黑饥饿 白吃饱前移吃饱
10、. 状态：灰色的圆点表示饥饿，红色表示吃饱 输入输入当前状态当前状态输出输出下一个状态下一个状态 黑黑饥饿饥饿涂白涂白吃饱吃饱 黑黑吃饱吃饱后移后移饥饿饥饿 白白饥饿饥饿涂黑涂黑饥饿饥饿 白白吃饱吃饱前移前移吃饱吃饱 . 状态：灰色的圆点表示饥饿，红色表示吃饱 输入输入当前状态当前状态输出输出下一个状态下一个状态 黑黑饥饿饥饿涂白涂白吃饱吃饱 黑黑吃饱吃饱后移后移饥饿饥饿 白白饥饿饥饿涂黑涂黑饥饿饥饿 白白吃饱吃饱前移前移吃饱吃饱 . 状态：灰色的圆点表示饥饿，红色表示吃饱 输入输入当前状态当前状态输出输出下一个状态下一个状态 黑黑饥饿饥饿涂白涂白吃饱吃饱 黑黑吃饱吃饱后移后移饥饿饥饿 白白饥
11、饿饥饿涂黑涂黑饥饿饥饿 白白吃饱吃饱前移前移吃饱吃饱 . 状态：灰色的圆点表示饥饿，红色表示吃饱 输入输入当前状态当前状态输出输出下一个状态下一个状态 黑黑饥饿饥饿涂白涂白吃饱吃饱 黑黑吃饱吃饱后移后移饥饿饥饿 白白饥饿饥饿涂黑涂黑饥饿饥饿 白白吃饱吃饱前移前移吃饱吃饱 . 状态：灰色的圆点表示饥饿，红色表示吃饱 输入输入当前状态当前状态输出输出下一个状态下一个状态 黑黑饥饿饥饿涂白涂白吃饱吃饱 黑黑吃饱吃饱后移后移饥饿饥饿 白白饥饿饥饿涂黑涂黑饥饿饥饿 白白吃饱吃饱前移前移吃饱吃饱 . 状态：灰色的圆点表示饥饿，红色表示吃饱 输入输入当前状态当前状态输出输出下一个状态下一个状态 黑黑饥饿饥饿
12、涂白涂白吃饱吃饱 黑黑吃饱吃饱后移后移饥饿饥饿 白白饥饿饥饿涂黑涂黑饥饿饥饿 白白吃饱吃饱前移前移吃饱吃饱 小虫模型就是一个图灵机 小虫的行为比以前的程序复杂了一些。 如果小虫的内部状态数再增多，那么它的行为会更加 的不可预测！ 输入、状态、输出、程序是图灵机的四大要素 人也可以看作一个特殊的图灵机 其状态数量非常大，状态表示是神经元的连接强度吗？ 其程序方式是什么？ 图灵机的组合 组合：如果往地上放了一个跷跷板，小球掉到地上会 弹起这个跷跷板的另一端，而跷跷板的另一边可能还 是一个小球，于是这个弹起的小球又会砸向另一个跷 跷板。 把多个计算系统合并成更大的计算系统。 通过组合若干图灵机完成更
13、大更多的计算，如果把一 个图灵机对纸带信息变换的结果又输入给另一台图灵 机，然后再输入给别的图灵机，这就是把计算进 行了组合！ 我们并不需要写出无限复杂的程序列表，而仅仅将这 些图灵机组合到一起就可以产生复杂的行为了。 有了图灵机的组合，我们就能够从最简单的图灵机开 始构造复杂的图灵机。 最简单的图灵机是什么呢？ 最简单的信息就是0和1，最简单的计算就是对0或1进 行布尔运算（与、或、非）。从最简单的逻辑运算操 作最简单的二进制信息出发我们其实可以构造任意的 图灵机！ 把输入、输出信息进行01的编码，而任何一个变换也 可以终分解为对01编码的变换，而对01编码的所有计 算都可分解成前面说的三种
14、运算。 为什么研究计算机的人都要去研究基本的布尔电路。 奥秘就在于，用布尔电路可以组合出任意的图灵机！ 图灵机为计算进行了建模 布尔代数为计算机实现奠定了数学基础 电子管、晶体管为用电路方式实现二进 制和二进制运算奠定了工程基础 计算机专业的课程体系 操作系统 汇编语言 计算机体系结构 微机原理与接口 计算机组成原理 数字逻辑 模拟电子技术 电路基础 电磁学 高级语言程设（各类语言） 编译原理 数据结构 算法（计算复杂性） 图形可视化 嵌入式系统 人工智能 计算机网络 软件工程 4、图灵机的计算极限 与计算复杂性 计算极限计算极限可计算性理论可计算性理论 计算机什么都能干？ 可以构造出计算机解
15、不出的问题 图灵机的停机问题 停机问题：存不存在一个程序比如说P，能够判断出任 意一个程序在给定输入下是否会陷入死循环？ 设P(X,Y)表示P判断程序X在数据输入是Y的情况下是 否陷入死循环的结果 如果存在死循环（不停机），那么P(X,Y)就输出一个yes 如果不存在死循环（停机），那么P(X,Y)就输出一个no 所谓的某个程序X在输入Y上停机就是说X不存在着死 循环，反过来如果不停机就是存在着死循环（或算不 出来）。那么，这种判断停机问题的程序P存在么？ 不存在，证明如下： 反证法： 假设程序P存在。 我们可以根据P设计一个程序Q，如下： Program Q(X) /X是任何一段程序的编码 m=P(X,X) ； if m=yes then return /P(X,X)不停机，则Q停机 else /P(X,X)停机，则Q不停机 do while (1) end do 证明过程 调用Q(Q)会发生什么情况？ 假设Q(Q)会发生死循环 由于P可以正确判断Q程序在
