好文档就是一把金锄头!
欢迎来到金锄头文库![会员中心]
电子文档交易市场
安卓APP | ios版本
电子文档交易市场
安卓APP | ios版本

大基62:图灵机与计算本质.pdf

22页
  • 卖家[上传人]:东****0
  • 文档编号:158060643
  • 上传时间:2020-12-29
  • 文档格式:PDF
  • 文档大小:1,006.06KB
  • / 22 举报 版权申诉 马上下载
  • 文本预览
  • 下载提示
  • 常见问题
    • 大学计算机 第6章:计算理 论与计算模型 6.2.1 图灵机模型 1. 图灵 图灵1912年6月23日生于伦敦近郊,因父母一度在国外, 童年时缺乏父爱和母爱,自幼起性格和行为很怪癖 13岁入中学,学习成绩不是很好,只有数学例外,演算 能力特别强此外,擅长赛跑 1931年中学毕业后考入剑桥大学攻读数学,其学位论文 课题是关于概率论的中心极限定理的,由于对前人工作 一无所知,他又重新发现了该定理 1935年,图灵开始对数理逻辑发生兴趣数理逻辑用数 学方法,也就是用符号和公式、公理的方法去研究人的 思维过程、思维规律 6.2.1 图灵机模型 1. 图灵 1936年,图灵发表论文“论可计算数及其在判定问题中的应 用”(On Computable Numbers With an Application to the Entscheidungs Problem),论文中描述了图灵机 图灵的工作第一次把计算和自动机联系起来,图灵机反映的是一种 计算模型,它可以完成任何的计算序列,是理想计算机的数学模型 图灵机思想提出不到10年,世界上第一台电子计算机ENIAC诞生了 图灵对以后计算科学和人工智能的发展产生了巨大的影响,为纪念 该文发表30周年,1966年设立“图灵奖”,以纪念这位计算机科 学理论的奠基人。

      6.2.1 图灵机模型 2. 图灵机模型 一条无限长的纸带 一个机器头在纸带上移来移去 机器头有一组内部状态,还有一些固定 的程序 6.2.1 图灵机模型 3. 图灵机的基本思想 图灵机4个部分组成: 一条无限长的纸带 TAPE 一个读写头 HEAD 一套控制规则 TABLE 一个状态寄存器 图灵机能模拟人类所能进行的任何计算过程 图灵机被公认为现代计算机的原型 图灵机从理论上是通用机 图灵机不是一种具体的机器,而是一种思想模型,可制造一种十分简单 但运算能力极强的计算装置,用来计算所有能想像得到的可计算函数 当前状态 移动读头 两端无穷的带子 可读写“寄存器” 图 6-5 图灵机 6.2.1 图灵机模型 4. 图灵机的理解 控制规则: 如果读出的当前符号为09,则右移一位,重复 如果读到空格,则写入符号0,停机 初始状态为: 此图灵机控制规则完成的是什么运算? 6.2.1 图灵机模型 4. 图灵机的理解 (2)小虫的比喻 假设一个小虫在地上爬,那么我们应该怎样从小虫信息处理的角度 来建立它的模型? 首先,我们需要对小虫所在的环境进行建模 其次,还需要为小虫建立输出装置,也就是说它能够动起来。

      重要的是,需要给它指定行动的规则, 这就是程序! 6.2.1 图灵机模型 4. 图灵机的理解 (2)小虫的比喻 输入信息集合为I=黑色,白色 输出行动集合:O=前移,后移 程序1: 输入输出 黑色前移 白色后移 初始状态 6.2.1 图灵机模型 4. 图灵机的理解 (2)小虫的比喻 现实世界中的小虫肯定不会这样傻的在那里无限循环下去我们还 需要改进这个最简单的模型 我们知道小虫除了可以机械地在世界上移动以外,还会对世界本身 造成影响,因而改变这个世界 比如虫子看到旁边有食物,它就会把那个东西吃掉了模型中也就 相当于假设小虫可以改写纸带上的信息 6.2.1 图灵机模型 4. 图灵机的理解 (2)小虫的比喻 输入信息集合:I=黑色,白色 输出行动集合:O=前移,后移,涂黑,涂白 程序2: 输入 输出 黑前移 白涂黑 6.2.1 图灵机模型 4. 图灵机的理解 (2)小虫的比喻 6.2.1 图灵机模型 4. 图灵机的理解 (2)小虫的比喻 进一步更改小虫模型,那么它就会有所改进,至少在给定相同输入 的情况下,小虫会有不同的输出情况这就是加入小虫的内部状态! 假设我们说小虫具有两个内部状态,并把它内部状态的集合记为: S=饥饿,吃饱。

      6.2.1 图灵机模型 4. 图灵机的理解 (2)小虫的比喻 程序3: 输入当前内部状态输出下时刻的内部状态 黑饥饿涂白吃饱 黑吃饱后移饥饿 白饥饿涂黑饥饿 白吃饱前移吃饱 6.2.1 图灵机模型 4. 图灵机的理解 (2)小虫的比喻 6.2.1 图灵机模型 4. 图灵机的理解 (2)小虫的比喻 6.2.1 图灵机模型 4. 图灵机的理解 (2)小虫的比喻 我们可以把小虫的输入集合、输出行动集合、内部状态集合进行扩 大,这个模型就一下子实用多了 首先,小虫完全可以处于一个三维的空间中而不是简简单单的 纸带并且小虫的视力很好,它一下子能读到方圆500米的信 息,当然,小虫也可以拥有其他的感觉器官,比如嗅觉、听觉 等等 而这些改变都仅仅是扩大了输入集合的维数和范围,并没有其 他更本质的改变 6.2.1 图灵机模型 4. 图灵机的理解 (2)小虫的比喻 小虫可能的输出集合也是异常的丰富,它不仅仅能移动自己,还可 以尽情的改造它所在的自然界 进一步的,小虫的内部状态可能非常的多,而且控制它行为的程序 可能异常复杂 那么小虫会有什么本事呢?这就很难说了,因为随着小虫内部的状 态数的增加,随着它所处环境的复杂度的增加,我们正在逐渐失去 对小虫行为的预测能力。

      6.2.1 图灵机模型 4. 图灵机的理解 (2)小虫的比喻 但是所有这些改变仍然没有逃出图灵机的模型: 输入集合 输出集合 内部状态 固定的程序 就是这四样东西抓住了小虫信息处理的根本 6.2.2 计算的本质 为什么说图灵机是计算机的数学模型,到底什么是计算 抽象地说,所谓计算,就是从一个符号串f变换成另一个符号串g 如符号串12+3变换成15是一个加法计算 如果符号串f是x2,而符号串g是2x,从f到g的计算就是微分 如果符号串f是”CHINA”,符号串g是”中国”,则f到g的计 算就是翻译 同样,排序、定理证明等都是计算 计算的形式多样、本质一样,都是从己知符号(串)开始,一步一步 地改变符号(串),经过有限步骤,最后得到一个满足预先规定的符 号(串)的变换过程 6.2.2 计算的本质 图灵从理论上证明了通用计算机存在的可能性,奠定了通用计算机 的理论基础 现代的计算机也是同样的工作模式,即使输入的数据相同,不同的 图灵机控制器,得到的输出结果也不一样 计算的形式多样、本质一样,都是从己知符号(串)开始,一步一步 地改变符号(串),经过有限步骤,最后得到一个满足预先规定的符 号(串)的变换过程。

      点击阅读更多内容
      相关文档
      福建省泉州市2026届高中毕业班质量监测(一)生物试卷非选择题评分说明.pptx n次方根与分数指数幂+课件-2025-2026学年高一上学期数学人教A版必修第一册.pptx 单调性与最大(小)值(第1课时)课件-2025-2026学年高一上学期数学人教A版必修第一册.pptx 函数的表示法+课件-2025-2026学年高一上学期数学人教A版必修第一册.pptx 无理数指数幂及其运算性质+课件-2025-2026学年高一上学期数学人教A版必修第一册.pptx 一元二次不等式的实际应用课件-2025-2026学年高一上学期数学人教A版必修第一册.pptx 用二分法求方程的近似解+课件-2025-2026学年高一上学期数学人教A版必修第一册.pptx 《大学之道》课件+2025-2026学年高二语文统编版选择性必修上册.pptx 《大学之道》课件2025-2026学年统编版高二语文选择性必修上册.pptx 等式性质与不等式性质第2课时课件-2025-2026学年高一上学期数学人教A版必修第一册.pptx 函数相同的概念课件-2025-2026学年高一上学期数学人教A版必修第一册.pptx 函数的概念+课件-2025-2026学年高一上学期数学人教A版必修第一册.pptx 抛物线及其标准方程课件-2025-2026学年高二上学期数学人教A版选择性必修第一册.pptx 对数函数的图象和性质+课件-2025-2026学年高一上学期数学人教A版必修第一册.pptx 函数的零点与方程的解 课件-2025-2026学年高一上学期数学人教A版必修第一册.pptx 古诗词诵读《将进酒》课件2025-2026学年统编版高二语文选择性必修上册.pptx 全称量词与存在量词课件-2025-2026学年高一上学期数学人教A版必修第一册.pptx 充分条件与必要条件课件-2025-2026学年高一上学期数学人教A版必修第一册.pptx 单调性与最大(小)值第2课时课件-2025-2026学年高一上学期数学人教A版必修第一册.pptx 等式性质与不等式性质课件-2025-2026学年高一上学期数学人教A版必修第一册.pptx
      关于金锄头网 - 版权申诉 - 免责声明 - 诚邀英才 - 联系我们
      手机版 | 川公网安备 51140202000112号 | 经营许可证(蜀ICP备13022795号)
      ©2008-2016 by Sichuan Goldhoe Inc. All Rights Reserved.