当前位置:首页 >> 工学 >>

关于图灵机模型的文献综述


关于图灵机模型 的文献综述

李云鹏 10061201

前言
自从 20 世纪 30 年代以来,图灵机、计算模型这些重要的概念在科学 的天空中就一直闪烁着无限的光彩。尤其是近年来量子计算机、生物 计算机、 DNA 计算等领域的创新工作引起了世人的广泛关注。 我们不 禁问这样的问题, 国外究竟为什么能发明出这些各式各样的计算机呢? 这些意味着什么呢?其实这一切的源头都来源于计算模型。 于是尝试 写下这么一篇文章,希望我的文章能够让你更加清楚、透彻的理解图 灵机、计算模型等等一些基本而重要的概念,并洞悉到这些概念的本 质和深远涵义。

正文
1936 年,英国数学家图灵提出了一种抽象的计算模型,以解释计算 机与人脑的运算过程。这就是著名的图灵机模型。 图灵机是由一个控制器, 一条有限长携带有信息和运算指令带子的带 子和一个可在带子上左右移动的读写头组成。这个简单的机器,理论 上却可以计算任何直观可计算函数。这就是著名的图灵论题。现在图 灵论题已被当成公理一样在使用着,它是数学的基础之一。 计算模型有两个需求,第一是可以形式化地表示算法(用符号串表示 算法),第二个就是可以机械地执行算法。同时一个计算模型的计算 能力是用它可计算的问题类的大小来刻画的。 目前人类尚无找到其它 的计算模型,其可计算的问题类超过图灵机的计算能力。所以可以说 图灵机模型是现在最好的计算模型。 图灵的基本思想是用机器来模拟人们用纸笔进行数学运算的过程, 他 把这样的过程看作下列两种简单的动作: 在纸上写上或擦除某个符号; 把注意力从纸的一个位置移动到另一个位置;而在每个阶段,人要决 定下一步的动作,依赖于 (a) 此人当前所关注的纸上某个位置的符号和 (b) 此人当前思维的状态。为了模拟人的这种运算过程,图灵构造出 一台假想的机器,该机器由以下几个部分组成: 1.一条无限长的纸带 TAPE。纸带被划分为一个接一个的小格子,每 个格子上包含一个来自有限字母表的符号, 字母表中有一个特殊的符 号 表示空白。纸带上的格子从左到右依此被编号为 0,1,2,... ,纸带

的右端可以无限伸展。 2.一个读写头 HEAD。该读写头可以在纸带上左右移动,它能读出当 前所指的格子上的符号,并能改变当前格子上的符号。 3.一套控制规则 TABLE。它根据当前机器所处的状态以及当前读写头 所指的格子上的符号来确定读写头下一步的动作, 并改变状态寄存器 的值,令机器进入一个新的状态。 4.一个状态寄存器。它用来保存图灵机当前所处的状态。图灵机的所 有可能状态的数目是有限的, 并且有一个特殊的状态, 称为停机状态。 参见停机问题。 我们可以构造出一个特殊的图灵机,它接受任意一个图灵机 M 的编 码<M> ,然后模拟 M 的运作,这样的图灵机称为通用图灵机 (Universal Turing Machine) 现代电子计算机其实就是这样一种通用图 。 灵机的模拟,它能接受一段描述其他图灵机的程序,并运行程序实现 该程序所描述的算法。但要注意,它只是模拟,因为现实中的计算机 的存储都是有限的,所以无法跨越有限状态机的界限。 图灵在科学、特别在数理逻辑和计算机科学方面,取得了举世瞩目的 成就,他的一些科学成果,构成了现代计算机技术的基础,当然其中 最重要的就是图灵提出的图灵机模型。在给出通用图灵机的同时,图 灵就指出,通用图灵机在计算时,其“机械性的复杂性”是有临界限 度的,超过这一限度,就要靠增加程序的长度和存贮量来解决.这种 思想开启了后来计算机科学中计算复杂性理论的先河。 图灵在判定问题上的一大成就是把图灵机的“停机问题”作为研究许

多判定问题的基础,一般地,把一个判定问题归结为停机问题: “如 果问题 A 可判定,则停机问题可判定. ”从而由“停机问题是不可判 定的”推出“问题 A 是不可判定的” 。 所谓停机指图灵机内部达到一个结果状态、 指令表上没有的状态 或符号对偶,从而导致计算终止。在每一时刻,机器所处的状态,纸 带上已被写上符号的所有格子以及机器当前注视的格子位置, 统称为 机器的格局。图灵机从初始格局出发,按程序一步步把初始格局改造 为格局的序列。此过程可能无限制继续下去,也可能遇到指令表中没 有列出的状态、符号组合或进入结束状态而停机。在结束状态下停机 所达到的格局是最终格局,此最终格局(如果存在)就包含机器的计算 结果。所谓停机问题即是:是否存在一个算法,对于任意给定的图灵 机都能判定任意的初始格局是否会导致停机?图灵证明, 这样的算法 是不存在的,即停机问题是不可判定的,从而使之成为解决许多不可 判定性问题的基础。 1937 年,图灵用他的方法解决了著名的希尔伯特判定问题:狭 谓词演算(亦称一阶逻辑)公式的可满足性的判定问题。他用一阶逻辑 中的公式对图灵机进行编码, 再由图灵机停机问题的不可判定性推出 一阶逻辑的不可判定性。他在此处创用的“编码法”成为后来人们证 明一阶逻辑的公式类的不可判定性的主要方法之一。 在判定问题上,图灵的另一成果是 1939 年提出的带有外部信息 源的图灵机概念,并由此导出“图灵可归约”及相对递归的概念。运 用归约和相对递归的概念, 可对不可判定性与非递归性的程度加以比

较。在此基础上,E.波斯特(Post)提出了不可解度这一重要概念,这 方面的工作后来有重大的进展。 图灵参与解决的另一个著名的判定问题是“半群的字的问题” , 它是图埃(Thue)在 1914 年提出来的:对任意给定的字母表和字典, 是否存在一种算法能判定两个任意给定的字是否等价 [给出有限个不 同的称为字母的符号,便给出了字母表,字母的有限序列称为该字母 表上的字.把有限个成对的字(A1,B1),?,(An,Bn)称为字典.如 果两个字 R 和 S 使用有限次字典之后可以彼此变换, 则称这两个字是 等价的]1947 年,波斯特和 A.A.马尔科夫(Markov)用图灵的编码 法证明了这一问题是不可判定的。1950 年,图灵进一步证明,满足 消元律的半群的字的问题也是不可判定的。 这些都为现在的计算机科 学的发展做出了巨大的贡献。 1945 年底图灵写出的关于 ACE 的设计说明书中,最先给出了存贮程 序控制计算机的结构设计(图灵后来参与研制的 Madam 机则是当时 世界上存贮量最大的电子计算机)。图灵的这份说明书中还最先提出 了指令寄存器和指令地址寄存器的概念, 提出了子程序和子程序库的 思想,这都是现代电子计算中最基本的概念和思想。令人吃惊的是, 在这份说明书中, 图灵已提出了 “仿真系统” 的思想, 所谓仿真系统, 指机器可以没有固定的指令系统, 但它能够模拟许多具有不同指令系 统的计算机的功能。 英国的 ACE 机只采用了图灵的部分思想, 而出于 保密的需要,图灵的 ACE 设计说明书,直到 1972 年才得以发表。这 期间, 人们不得不重新发现图灵已经发现过的东西, 恰恰也是在 1972

年,人们才制成具有仿真系统的计算机。 “人工智能”一词最初是在 1956 年 Dartmouth 学会上提出的。从那 以后, 研究者们发展了众多理论和原理, 人工智能的概念也随之扩展。 人工智能是一门极富挑战性的科学, 从事这项工作的人必须懂得计算 机知识,心理学和哲学。人工智能是包括十分广泛的科学,它由不同 的领域组成,如机器学习,计算机视觉等等,总的说来,人工智能研 究的一个主要目标是使机器能够胜任一些通常需要人类智能才能完 成的复杂工作。人工智能(Artificial Intelligence,简称 AI)是计算机 学科的一个分支, 二十世纪七十年代以来被称为世界三大尖端技术之 一(空间技术、能源技术、人工智能) 。也被认为是二十一世纪(基 因工程、纳米科学、人工智能)三大尖端技术之一。这是因为近三十 年来它获得了迅速的发展,在很多学科领域都获得了广泛应用,并取 得了丰硕的成果,人工智能已逐步成为一个独立的分支,无论在理论 和实践上都已自成一个系统。而图灵是人工智能研究的先驱者之一, 实际上, 图灵机, 尤其是通用图灵机作为一种非数值符号计算的模型, 就蕴含了构造某种具有一定的智能行为的人工系统以实现脑力劳动 部分自动化的思想,这正是人工智能的研究目标。图灵的机器智能思 想无疑是人工智能的直接起源之一。 而且随人工智能领域的深入研究, 人们越来越认识到图灵思想的深刻性: 它们至今仍然是人工智能的主 要思想之一。我认为人工智能是可以实现到逻辑思维这一步的,因为 逻辑思维可以完全用字符串来表示, 图灵机可以把任意单元置成任意 值,在这一点上是完备的,这就足以描述逻辑思维了,所以用图灵机

完全可以实现到逻辑思维。 当然图灵机会受到哥德尔不完备性的制约, 但是逻辑系统也会受到同样的制约, 所以我认为完全可以用图灵机模 型实现逻辑思维。

总结
所谓的图灵机就是指一个抽象的机器,它有一条无限长的纸带,纸带 分成了一个一个的小方格,每个方格有不同的颜色。有一个机器头在 纸带上移来移去。机器头有一组内部状态,还有一些固定的程序。在 每个时刻,机器头都要从当前纸带上读入一个方格信息,然后结合自 己的内部状态查找程序表,根据程序输出信息到纸带方格上,并转换 自己的内部状态,然后进行移动。这个模型,也就是传统意义上的图 灵机模型。 图灵机模型,是现代计算机的基础,直到现在为止,没有发现超越图 灵机模型的其他计算模型, 至于未来能不能发现超越图灵机的计算模 型,或者更加完善图灵机计算模型,更好地应用图灵机,就只能靠现 在的科学技术的发展以及人类的智慧了。

参考文献 1.赵正平, 《图灵机及其构造研究》 ,中图分类号: TP301 文献标识码: A 文章编号: 10093044(2006)26- 0192- 03 2.张立昂, 《可计算性与计算复杂性导引》 ,北京:北京大学出版社,1996:1-34 3.张立昂等译,Michael Sipser《计算理论导论》 ,北京:机械工业出版社,1996:1-28,95-116 4.王强, 四则运算图灵机的构造》 《 ,内蒙古师范大学学报, 2004,9(3):1-41 5.Bill Manaris ( 马 纳 瑞 斯 ) . 《 从 人 - 机 交 互 的 角 度 看 自 然 语 言 处 理 》 . Advances in Computers,1999 年,第 47 卷


相关文章:
关于图灵机模型的文献综述.doc
关于图灵机模型的文献综述 - 关于图灵机模型 的文献综述 李云鹏 1006120
图灵机的思想与模型简介.ppt
图灵机的思想与模型简介 - 冯.诺依曼计算机:机器级程序及其执行 2.2.1 图灵机的思想与模型简介 图灵机的思想与模型简介 ---图灵的贡献 ---图灵机:计算机...
文献综述_人工智能.doc
文献综述_人工智能_信息与通信_工程科技_专业资料。人工智能的历史、现状、前景...(A. Tur-ing) 1936 年提出了一种理想计算机的数学模型, 在 即图灵机之后,...
图灵机_含小虫类比.pdf
(一) 图灵与图灵机图灵机是计算机的理论模型,这个名字来源于它的发明人,阿兰...参考文献: Harry R. Lewis (1998). Elements of the Theory of Computation,...
第一讲_计算模型与图灵机.ppt
第一讲_计算模型图灵机_工学_高等教育_教育专区。计算机科学导论乐嘉锦计算机科
图灵机简介和原理分析.doc
图灵机简介和原理分析 - 图灵机简介和原理分析 摘要: 1936 年, 阿兰图灵提出了一种抽象的计算模型 图 灵机 (Turing Machine)。图灵机是指一个抽象的...
图灵机模型.ppt
著名的抽象计算机模型... 3页 1财富值 关于图灵机模型的文献综述 10页
第1章 图灵机模型及数据编码.ppt
第1章 图灵机模型及数据编码_工学_高等教育_教育专区。计算机导论第...关于图灵机模型的文献综... 10页 免费 第二讲 图灵机模型 103页 4下载券喜欢...
1 图灵机模型.ppt
1 图灵机模型_理学_高等教育_教育专区。图灵机模型理论是计算学科最核心的理论之一图灵机模型为计算机设计指明了方向图灵机模型是算法分析和程序语言设计的基础理论计...
文献综述_人工智能.txt
文献综述_人工智能_韩语学习_外语学习_教育专区。文献综述_人工智能 ...(A. Tur-ing)在1936年提出了一种理想计算机的数学模型,即图灵机之后,1946年...
图灵机与现代计算机.ppt
图灵机是计算机的一种简单数字模型,尽管简 单,但它具有模拟通用计算机的计算能力。 图灵机的基本模型图灵机由一条两端可无限延长的带子、一个 读写头以及一组控制...
图灵和图灵机模型.ppt
图灵的研究成果是:可计算性 = 图灵可计算性 任一过程是能行的(理论上的能...加法图灵机 12页 免费 14. 图灵机 3页 免费 关于图灵机模型的文献综......
第七章 图灵机.ppt
第七章 图灵机 - 第七章 图灵机 周俊萍 zhoujp877@nenu.edu.cn 本章,我们将介绍图灵机-计算机的一种简单数学 模型。尽管图灵机简单,但它具有模拟通用计算机 ...
1.图灵机与计算问题(1节课).pdf
有限的、机械的丢番图问题可以等价于停机问题 因此在图灵机计算模型下是不可
图灵机模型.ppt
图灵机模型_计算机硬件及网络_IT/计算机_专业资料。图灵机模型 图灵机模型概论 ? ? ? 图灵机模型理论是计算学科最核心的理论之一 图灵机模型为计算机设计指明了方...
图灵机.pdf
8 2. 如何理解图灵机模型* 这个模型是否太简单了?下面,我就要试图说服你,图灵...参考文献: Harry R. Lewis (1998). Elements of the Theory of Computation,...
计算机的过去现在与未来-02、图灵和图灵机模型.ppt
计算机的过去现在与未来-02、图灵和图灵机模型 - 第2课 图灵和图灵机模型
基于图灵机的计算问题.pdf
图灵机20世纪30年代英国数学家图灵创造的一种计算模型,它可以确切地表达计算...(14) 1次 引证文献(1条) 1.张汉昭 图灵机在康托集上的可计算性[期刊论文...
北理大学计算机实验基础 实验一_图灵机模型与计算机硬....doc
北理大学计算机实验基础 实验一_图灵机模型与计算机硬件系统虚拟拆装-实验报告_互联网_IT/计算机_专业资料。实验一 图灵机模型与计算机硬件系统虚拟拆装五、实验报告 ...
图灵机.ppt
图灵机 - 第4章 图灵机 1 Overview ? 图灵机(Turing Machine,TM),是 计算机的一种简单的数学模型图灵机诱发的。 ? 历史上,冯?诺曼计算机的产生就...
更多相关标签: