图灵机简介和原理分析

《图灵机简介和原理分析》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、图灵机简介和原理分析摘要：1936年，阿兰・图灵提出了一种抽象的计算模型——图灵机(TuringMachine)o图灵机是指一个抽象的机器，可被视作任意解决有限数学逻辑过程的机器，它提供了一种简单有效的解决逻辑过程的方法，加快了后来诺依曼设计的计算机的出现。本文将对图灵机的原理和历史等进行简介和分析。关键字：图灵机，计算模型。一.图灵机的历史发展图灵机被公认为现代计算机的原型，这台机器可以读入一系列的零和一，这些数字代表了解决某一问题所需要的步骤，按这个步骤走下去，就可以解决某一特定的问题。这种观念在当时是具有革命性意义的，因为即使在

2、50年代的时候，大部分的计算机还只能解决某一特定问题，不是通用的，而图灵机从理论上却是通用机。1936年,图灵向伦敦权威的数学杂志投了一篇论文，题为"论数字计算在决断难题中的应用"。在这篇开创性的论文中，图灵给〃可计算性〃下了一个严格的数学定义，并提出著名的图灵机"(TuringMachine)的设想。〃图灵机〃不是一种具体的机器，而是一种思想模型，可制造一种十分简单但运算能力极强的计算装置,用来计算所有能想像得到的可计算函数。〃图灵机〃与"冯•诺伊曼机〃齐名，被永远载入计算机的发展史中。1950年10月，图灵又发表了另一篇题为"机器

3、能思考吗"的论文，成为划时代之作。也正是这篇文章，为图灵赢得了〃人工智能之父'‘的桂冠。在图灵看来，这台机器只用保留一些最简单的指令，一个复杂的工作只用把它分解为这几个最简单的操作就可以实现了，在当时他能够具有这样的思想确实是很了不起的。图灵机的产生一方面奠定了现代数字计算机的基础（要知道后来冯•诺依曼就是根据图灵的设想才设计出第一台计算机的）。另一方面，根据图灵机这一基本简洁的概念，我们还可以看到可计算的极限是什么。也就是说实际上计算机的本领从原则上讲是有限制的。请注意，这里说到计算机的极限并不是说它不能吃饭、扫地等硬件方面的极限，

4、而是仅仅就从信息处理这个角度，计算机也仍然存在着极限。这就是图灵机的停机问题。二.图灵机原理及分析图灵的基本思想是用机器来模拟人们用纸笔进行数学运算的过程，他把这样的过程看作下列两种简单的动作：1）在纸上写上或擦除某个符号；2）把注意力从纸的一个位置移动到另一个位置；而在每个阶段，人要决定下一步的动作，依赖于（a）此人当前所关注的纸上某个位置的符号和（b）此人当前思维的状态。为了模拟人的这种运算过程，图灵构造出一台假想的机器，该机器由以下几个部分组成：一条无限长的纸带。纸带被划分为一个接一个的小格子，每个格子上包含一个來自有限字母表的

5、符号，字母表中有一个特殊的符号表示空白。纸带上的格子从左到右依此被编号为0,1,2,,纸带的右端可以无限伸展。一个读写头。该读写头可以在纸带上左右移动，它能读出当前所指的格子上的符号，并能改变当前格子上的符号。一个状态寄存器。它用来保存图灵机当前所处的状态。图灵机的所有可能状态的数目是有限的，并且有一个特殊的状态，称为停机状态。一套控制规则。它根据当前机器所处的状态以及当前读写头所指的格子上的符号来确定读写头下一步的动作，并改变状态寄存器的值，令机器进入一个新的状态。这个机器的每一部分都是有限的，但它有一个潜在的无限长的纸带，因此这种

6、机器只是一个理想的设备。图灵认为这样的一台机器就能模拟人类所能进行的任何计算过程下面我们用另一种思想来理解图灵机：注：以下内容来自百度文库：小虫的比喻：我们不妨考虑这样一个问题.假设一个小虫在地上爬,那么我们应该怎样从小虫信息处理的角度来建立它的模型呢？首先，我们需要对小虫所在的环境进行建模。我们不妨假设小虫所处的世界是一个无限长的纸带，这个纸带上被分成了若干小方格，而每个方格都只有黑白两种颜色。黑色表示该方格有食物，白色就表示没有。假设小虫仅具有一个感觉器官：眼睛，而且它的视力差得可怜，也就是说它仅仅能够感受到它所处的方格的颜色。因

7、而这个方格所在的位置的黑色或者白色的信息就是小虫的输入信息。其次，小虫有输出动作，它可以在方格上前移，后移，还可以涂写方格成黑色或者白色。最后，小虫还会有两种内部状态，即｛饥饿,吃饱｝。这样小虫的行动按照下面的程序进行：程序：输入当前内部状态输出下时刻的内部状态JE八八饥饿涂白吃饱里吃饱后移饥饿白饥饿涂黑饥饿口吃饱前移吃饱即如果当前处于饥饿状态，则有食物就吃掉，没有食物就“吐出食物”；如果当前处于吃饱的状态，则如果没有食物就前移，如果有就后退，并且转入饥饿状态。那么当小虫子读入黑白白黑白……这样的纸带的时候，会怎样行动呢？小虫用圆圈表

8、示，它从最左边开始移动,灰色表示饥饿状态，口色表示吃饱状态.箭头表示移动的方向.从上到下，小虫一步一步地根据纸带的颜色和它自己的内部状态查找规则表中的对应项而采取行动。例如第5步读入方格是黑色，内部状态为吃饱，根据这两项