当前位置:首页 >> 计算机软件及应用 >>

图灵机简介和原理分析


图灵机简介和原理分析
摘要: 1936 年, 阿兰·图灵提出了一种抽象的计算模型 —— 图
灵机 (Turing Machine)。图灵机是指一个抽象的机器,可被视作任 意解决有限数学逻辑过程的机器, 它提供了一种简单有效的解决逻辑 过程的方法,加快了后来诺依曼设计的计算机的出现。本文将对图灵 机的原理和历史等进行简介和分析。

关键字:图灵机,计算模型。 一. 图灵机的历史发展 图灵机被公认为现代计算机的原型, 这台机器可以读入一系 列的零和一,这些数字代表了解决某一问题所需要的步骤,按这 个步骤走下去,就可以解决某一特定的问题。这种观念在当时是 具有革命性意义的,因为即使在 50 年代的时候,大部分的计算 机还只能解决某一特定问题,不是通用的,而图灵机从理论上却 是通用机。 1936 年,图灵向伦敦权威的数学杂志投了一篇论文,题为"论 数字计算在决断难题中的应用"。 在这篇开创性的论文中,图灵给 "可计算性"下了一个严格的数学定义,并提出著名的图灵机 "(Turing Machine)的设想。"图灵机"不是一种具体的机器,而是 一种思想模型,可制造一种十分简单但运算能力极强的计算装置, 用来计算所有能想像得到的可计算函数。 "图灵机"与"冯?诺伊曼 机"齐名,被永远载入计算机的发展史中。1950 年 10 月,图灵又

发表了另一篇题为"机器能思考吗"的论文,成为划时代之作。也 正是这篇文章,为图灵赢得了"人工智能之父"的桂冠。 在图灵看来,这台机器只用保留一些最简单的指令,一个复 杂的工作只用把它分解为这几个最简单的操作就可以实现了, 在 当时他能够具有这样的思想确实是很了不起的。 图灵机的产生一方面奠定了现代数字计算机的基础 (要知道 后来冯?诺依曼就是根据图灵的设想才设计出第一台计算机的) 。 另一方面,根据图灵机这一基本简洁的概念,我们还可以看到可 计算的极限是什么。 也就是说实际上计算机的本领从原则上讲是 有限制的。 请注意, 这里说到计算机的极限并不是说它不能吃饭、 扫地等硬件方面的极限,而是仅仅就从信息处理这个角度,计算 机也仍然存在着极限。这就是图灵机的停机问题。 二. 图灵机原理及分析 图灵的基本思想是用机器来模拟人们用纸笔进行数学运算 的过程,他把这样的过程看作下列两种简单的动作: 1)在纸上写上或擦除某个符号; 2)把注意力从纸的一个位置移动到另一个位置; 而在每个阶段,人要决定下一步的动作,依赖于 (a) 此人 当前所关注的纸上某个位置的符号和(b) 此人当前思维的状态。 为了模拟人的这种运算过程,图灵构造出一台假想的机器,该机 器由以下几个部分组成: 一条无限长的纸带。纸带被划分为一个接一个的小格子,每

个格子上包含一个来自有限字母表的符号, 字母表中有一个特殊 的符号 表示空白。纸带上的格子从左到右依此被编号为 0, 1, 2, ... ,纸带的右端可以无限伸展。 一个读写头。该读写头可以在纸带上左右移动,它能读出当 前所指的格子上的符号,并能改变当前格子上的符号。 一个状态寄存器。它用来保存图灵机当前所处的状态。图灵 机的所有可能状态的数目是有限的,并且有一个特殊的状态,称 为停机状态。 一套控制规则。 它根据当前机器所处的状态以及当前读写头 所指的格子上的符号来确定读写头下一步的动作, 并改变状态寄 存器的值,令机器进入一个新的状态。 这个机器的每一部分都是有限的, 但它有一个潜在的无限长 的纸带,因此这种机器只是一个理想的设备。图灵认为这样的一 台机器就能模拟人类所能进行的任何计算过程

下面我们用另一种思想来理解图灵机: 注:以下内容来自百度文库: 小虫的比喻: 我们不妨考虑这样 一个问题.假设一个小虫在地上 爬,那么我们应该怎样从小虫信息处理的角度来建立它的模型呢? 首 先, 我们需要对小虫所在的环境进行建模。 我们不妨假设小虫所处的 世界是一个无限长的纸带,这个纸带上被分成了若干小方格,而每个 方格都只有黑白两种颜色。 黑色表示该方格有食物, 白色就表示没有。

假设小虫仅具有一个感觉器官:眼睛,而且它的视力差得可怜, 也就 是说它仅仅能够感受到它所处的方格的颜色。 因而这个方格所在的位 置的黑色或者白色的信息就是小虫的输入信息。 其次, 小虫有输出动 作,它可以在方格上前移,后移,还可以涂写方格成黑色或者白色。 最后,小虫还会有两种内部状态,即{饥饿,吃饱}。这样小虫的行动 按照下面的程序进行:

程序: 输入 黑 黑 白 白 当前内部状态 饥饿 吃饱 饥饿 吃饱 输出 涂白 后移 涂黑 前移 下时刻的内部状态 吃饱 饥饿 饥饿 吃饱

即如果当前处于饥饿状态,则有食物就吃掉,没有食物就“吐出 食物” ;如果当前处于吃饱的状态,则如果没有食物就前移,如果有 就后退,并且转入饥饿状态。那么当小虫子读入黑白白黑白??这样 的纸带的时候, 会怎样行动呢?小虫用圆圈表示,它从最左边开始 移动,灰色表示饥饿状态,白色表示吃饱状态. 箭头表示移动的方向. 从上到下,小虫一步一步 地根据纸带的颜色和它自己的内部状态查

找规则表中的对应项而采取行动。例如第 5 步读入方格是黑色,内 部状态为吃饱,根据这两项输入信息查找规则表找到对应项是第二 项, 根据小虫应该后移, 且内部状态变为饥饿。 不难看到, 了第 8 到 步,情况跟第 4 步完全相同,输入都是白色纸带和饥饿状态,根据程 序,小虫将重复 4-8 之间的动作,并一直持续下去??。尽管从长 期来看,小虫会落入机械的循环,然而当你输入给小虫白色信息的时 候,它的反应可能完全不同 (如第 4 步和第 6 步的行为) 所以 , 只要小虫子的内部状态和程序非常复杂, 那么小虫的行为也会越来越 超出你的想象! 相信你 已经明白了这个小虫模型,那么你就掌握了 图灵机的工作原理, 因为从本质上讲, 这个小虫模型就是一台图灵机。 图灵机是一个会对输入信息进行变换给出输出信息的系统。比如 前面说的小虫, 纸带上的一个方格一个方格的颜色信息就是对小虫的 输入,而小虫所采取的行动就是它的输出。不过这么看,你会发现, 似乎小虫的输出太简单了。因为它仅仅就有那么几种简单的输出动 作。然而,不要忘了,复杂性来源于组合!虽然每一次小虫的输出动 作很简单,然而当把所有这些输出动作组合在一起,就有可能非常复 杂!比如我们可以把初始时刻的纸带看作是输入信息,那么经过任意 长的时间比如说 100 年后, 小虫通过不断的涂抹纸带最后留下的信息 就是输出信息了。那么小虫完成的过程就是一次计算。事实上,在图 灵机的正规定义中,存在一个所谓的停机状态,当图灵机一到停机状 态,我们就认为它计算完毕了,因而不用费劲的等上 100 年。 我们自然可以通过组合若干图灵机完成更大更多的计算,如果把

一个图灵机对纸带信息变换的结果又输入给另一台图灵机, 然后再输 入给别的图灵机??,这就是把计算进行了组合。也许你还在为前面 说的无限多的内部状态,无限复杂的程序而苦恼,那么到现在,你不 难明白,实际上我们并不需要写出无限复杂的程序列表,而仅仅将这 些图灵机组合到一起就可以产生复杂的行为了。


相关文章:
图灵机简介和原理分析.doc
图灵机简介和原理分析 - 图灵机简介和原理分析 摘要: 1936 年, 阿兰图
图灵机原理及分析.doc
图灵机原理及分析 - 一. 图灵机原理及分析 图灵的基本思想是用机器来模拟人们用
图灵机的思想与模型简介.ppt
图灵机的思想与模型简介 - 冯.诺依曼计算机:机器级程序及其执行 2.2.1 图灵机的思想与模型简介 图灵机的...
永不停息的纸带 浅谈图灵机.pdf
永不停息的纸带 浅谈图灵机的工作原理及其编程...即将现实世界 的种种表象分析整合,抽丝剥茧,总结出...图灵机的思想与模型简介 8页 2下载券 关于图灵机...
图灵和图灵机模型.ppt
图灵机计算模型 2.3 图灵简介 1 2.1 计算本质的...抽象和理论两个过程
图灵机与现代计算机.ppt
图灵机的概述 A.Turing在1936年介绍了这样一个通用...,图灵机模型是算法 分析和程序语言设计的基础理论。...
图灵机开发说明文档.doc
图灵机模拟器编程软件开发环境简介 (1)Java JDK ...通过上面的分析,可构造图灵机 M=(Q,T,Σ,δ,q...图灵机理论的一个最美妙的结论就是存在“元图灵机(...
永不停息的纸带浅谈图灵机.doc
永不停息的纸带浅谈图灵机_IT/计算机_专业资料。简要介绍图灵机的设计思想和工作原理,感悟图灵机中蕴含的计算机程序设计思想。 ...
图灵机及其模拟系统的研究.doc
图灵机及其模拟系统的研究 - 图灵机模型是现代计算机科学的理论基础,学习图灵机理论对于研究计算机软件理论有着重要的意义,本文介绍图灵机的产生和用途,分析了图灵...
图灵机计算机的理论模型.ppt
图灵机 模型是算法分析和程序语言设计的基础,为...图灵机理论 4页 1下载券 图灵机理论简介 3页 1...
计算机的过去现在与未来-02、图灵和图灵机模型.ppt
计算机的过去现在未来-02、图灵和图灵机模型 - 第2课 图灵和图灵机模型 罗
chapter 9-图灵机解析.ppt
第九章、图灵机 3、10年后,一位数学家冯诺依曼给出了现代存储程序式电子数 字计算机的基本结构与工作原理。回顾一下已经介绍的计算模型,我们发现它是一步步走向...
计算模型图灵机.ppt
计算模型图灵机_计算机软件及应用_IT/计算机_专业资料。计算模型图灵机 第5周、第6周内容介绍理论计算机...
计算机原理之图灵机与冯诺依曼机.doc
计算机原理图灵机与冯诺依曼机 - 计算机原理图灵机与冯诺依曼机 计算机科学班
算法与图灵机模型.ppt
图灵机模型为计算机设计指明了方向 ? 图灵机模型是算法分析和程序语言设计的 基础理论。 01:00 本节主要...
第一章计算机组成与基本原理_图文.ppt
计算机安全简介 第一章计算机组成与基本原理 §1.1...与基本原理 1833 分析机 §1.1.2 计算机起源和...第一章计算机组成与基本原理 图灵与图灵机计算机是...
Part4图灵机及可计算理论(精).ppt
Part 4 图灵机及可计算理论主讲教师 贺利坚 Part 4 主要内容提示内 容教材出处 一、图灵机及形式定义 二...
计算机组成原理_图文.ppt
图灵机(了解) 1.3 计算机的基本组成 1.4 计算机的...本书主要介绍计算机的组成及工作原理。 1.1.3 ...计算机的工作过程可归结为:取指令→分析指令→执行...
计算机基础之工作原理_图文.ppt
(第一讲) 第一讲) 课程介绍 ? 计算机文化基础...分析机 第一台电子计算机( 第一台电子计算机(ENIAC...离的结构。 Shannon 图灵与图灵机 计算机工作原理 ...
第1章计算机的基础知识_图文.ppt
成及工作原理,微型计算机简介,计算机安全与计 算机...图灵 主要贡献:创立通用计算机的理论 ,即“图灵机”...情报等 信息进行合并、分类、排序、分析、检索等加工...