关于图灵机模型地文献综述.pdfVIP

关于图灵机模型 的文献综述 李云鹏 前言 自从20 世纪30 年代以来，图灵机、计算模型这些重要的概念在科学 的天空中就一直闪烁着无限的光彩。尤其是近年来量子计算机、生物 计算机、DNA 计算等领域的创新工作引起了世人的广泛关注。我们不 禁问这样的问题，国外究竟为什么能发明出这些各式各样的计算机呢？ 这些意味着什么呢？其实这一切的源头都来源于计算模型。于是尝试 写下这么一篇文章，希望我的文章能够让你更加清楚、透彻的理解图 灵机、计算模型等等一些基本而重要的概念，并洞悉到这些概念的本 质和深远涵义。 正文 1936 年，英国数学家图灵提出了一种抽象的计算模型，以解释计算 机与人脑的运算过程。这就是著名的图灵机模型。 图灵机是由一个控制器，一条有限长携带有信息和运算指令带子的带 子和一个可在带子上左右移动的读写头组成。这个简单的机器，理论 上却可以计算任何直观可计算函数。这就是著名的图灵论题。现在图 灵论题已被当成公理一样在使用着，它是数学的基础之一。 计算模型有两个需求，第一是可以形式化地表示算法(用符号串表示 算法)，第二个就是可以机械地执行算法。同时一个计算模型的计算 能力是用它可计算的问题类的大小来刻画的。目前人类尚无找到其它 的计算模型，其可计算的问题类超过图灵机的计算能力。所以可以说 图灵机模型是现在最好的计算模型。 图灵的基本思想是用机器来模拟人们用纸笔进行数学运算的过程，他 把这样的过程看作下列两种简单的动作：在纸上写上或擦除某个符号； 把注意力从纸的一个位置移动到另一个位置；而在每个阶段，人要决 定下一步的动作，依赖于 (a) 此人当前所关注的纸上某个位置的符号和 (b) 此人当前思维的状态。为了模拟人的这种运算过程，图灵构造出 一台假想的机器，该机器由以下几个部分组成： 1.一条无限长的纸带 TAPE 。纸带被划分为一个接一个的小格子，每 个格子上包含一个来自有限字母表的符号，字母表中有一个特殊的符 号 表示空白。纸带上的格子从左到右依此被编号为 0,1,2,... ，纸带 的右端可以无限伸展。 2.一个读写头 HEAD。该读写头可以在纸带上左右移动，它能读出当 前所指的格子上的符号，并能改变当前格子上的符号。 3.一套控制规则 TABLE 。它根据当前机器所处的状态以及当前读写头 所指的格子上的符号来确定读写头下一步的动作，并改变状态寄存器 的值，令机器进入一个新的状态。 4.一个状态寄存器。它用来保存图灵机当前所处的状态。图灵机的所 有可能状态的数目是有限的，并且有一个特殊的状态，称为停机状态。 参见停机问题。 我们可以构造出一个特殊的图灵机，它接受任意一个图灵机 M 的编 码M ，然后模拟 M 的运作，这样的图灵机称为通用图灵机 (Universal Turing Machine ）。现代电子计算机其实就是这样一种通用图 灵机的模拟，它能接受一段描述其他图灵机的程序，并运行程序实现 该程序所描述的算法。但要注意，它只是模拟，因为现实中的计算机 的存储都是有限的，所以无法跨越有限状态机的界限。 图灵在科学、特别在数理逻辑和计算机科学方面，取得了举世瞩目的 成就，他的一些科学成果，构成了现代计算机技术的基础，当然其中 最重要的就是图灵提出的图灵机模型。在给出通用图灵机的同时，图 灵就指出，通用图灵机在计算时，其“机械性的复杂性”是有临界限 度的，超过这一限度，就要靠增加程序的长度和存贮量来解决．这种 思想开启了后来计算机科学中计算复杂性理论的先河。 图灵在判定问题上的一大成就是把图灵机的“停机问题”作为研究许 多判定问题的基础，一般地，把一个判定问题归结为停机问题：“如 果问题A 可判定，则停机问题可判定．”从而由“停机问题是不可判 定的”推出“问题A 是不可判定的”。 所谓停机指图灵机内部达到一个结果状态、指令表上没有的状态 或符号对偶，从而导致计算终止。在每一时刻，机器所处的状态，纸 带上已被写上符号的所有格子以及机器当前注视的格子位置，统称为 机器的格局。图灵机从初始格局出发，按程序一步步把初始格局改造 为格局的序列。此过程可能无限制继续下