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

图灵机简介和原理分析


图灵机简介和原理分析
摘要: 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 年。 我们自然可以通过组合若干图灵机完成更大更多的计算,如果把

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


相关文章:
图灵机设计
图灵机设计_电子/电路_工程科技_专业资料。i*j*k=l 1.4 A. B. C. D. ...图灵机介绍 暂无评价 3页 1下载券 基本图灵机及图灵机的构... 31页 免费 ...
停机状态图灵机
停机状态图灵机 - 此外,它还有一个控制函数,该函数根据团灵机所处的当前状态和读写头所读到的当前符号决定团灵机的下一步操作,其中每一步操作包括三件事一,...
不可计算理论
不可计算理论_IT/计算机_专业资料。计算机 可计算理论 图灵机不可计算理论计算机有着强大的计算能力, 那是不是当计算机的计算能力达到极高水平时 就可以解决所有问...
软件学院编译原理试题1
机理论 b.图灵机 (1) a.有穷自动机理论 b.图灵机 c.图论 d.无穷自动机...数据流分析法 d.结构图 2、 通常编译程序是把高级语言书写的源程序翻译为 (1...
编译原理练习题及答案
编译原理练习题及答案_IT/计算机_专业资料。编译原理...图灵机 F 有限自动机 G 下推自动机 4.一个文法...下语法分析) 第五章练习题(自上而下语法分析) 1...
编译原理2006期末考试试卷A
《编译原理》 卷(A共 5 页) 5.在下述的编译方法中, ①简单优先分析 ②算...(A)图灵机 (B)下推自动机 (C)有限自动机 (D)以上皆不对 天津大学试卷...
编译原理 - A卷
浙江工业大学之江学院 编译原理 试卷 A 2009/2010(...C.LR(1)分析法 D.SLR(1)分析法 3、 若 a ...DFA D. 图灵机 12、正则表达式 R1 和 R2 等价是...
编译原理作业集-第二章
编译原理作业集-第二章_工学_高等教育_教育专区。...语法分析树和二义性; 本章难点 1. 二义性文法;...a. 图灵机;b. 确定性有限自动机;c. 下推自动机...
电子科大16秋《计算机编译原理》在线作业2及答案
电子科大16秋《计算机编译原理》在线作业2及答案_...在编译程序中,语法分析分为自顶向下分析和自底向上...图灵机 F. 有限自动机 G. 下推自动机 正确答案:...
编译原理复习资料
编译原理复习资料_工学_高等教育_教育专区。(1) ...0 型(短语文法, 图灵机): 产生式形如: ? ? ?...8) 编译程序中语法分析器接收以什么为单位的输入? ...
更多相关标签: