图灵机的组成部分_图灵机的模型介绍.doc

《图灵机的组成部分_图灵机的模型介绍.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、图灵机的组成部分_图灵机的模型介绍　　1.一条无限长的纸带TAPE。纸带被划分为一个接一个的小格子，每个格子上包含一个来自有限字母表的符号，字母表中有一个特殊的符号表示空白。纸带上的格子从左到右依此被编号为0，1，2，。..，纸带的右端可以无限伸展。　　2.一个读写头HEAD。该读写头可以在纸带上左右移动，它能读出当前所指的格子上的符号，并能改变当前格子上的符号。　　3.一套控制规则TABLE。它根据当前机器所处的状态以及当前读写头所指的格子上的符号来确定读写头下一步的动作，并改变状态寄存器的值，令机器进入一个新的状态。　　4.一个状态寄存器。它用来保存图灵机当前所

2、处的状态。图灵机的所有可能状态的数目是有限的，并且有一个特殊的状态，称为停机状态。参见停机问题。　　关于图灵机的模型介绍　　图灵机的模型介绍虽然有些无趣，不过请坚持看下去，我会在下面运用大家比较好理解的形式重新解释的。在这里你仅仅需要认识它的轮廓。一个图灵机是形如下面的一个装置：　　这个装置由下面几个部分组成：一个无限长的纸带，一个读写头。（中间那个大盒子），内部状态（盒子上的方块，比如A，B，E，H），另外，还有一个程序对这个盒子进行控制。这个装置就是根据程序的命令以及它的内部状态进行磁带的读写、移动。它工作的时候是这样的：从读写头在纸带上读出一个方格的信息，并且

3、根据它当前的内部状态开始对程序进行查表，然后得出一个输出动作，也就是是否往纸带上写信息，还是移动读写头到下一个方格。程序也会告诉它下一时刻内部状态转移到哪一个。　　具体的程序就是一个列表，也叫做规则表，是这样的：　　当前内部状态s输入数值i输出动作o下一时刻的内部状态s‘　　B1前移C　　A0往纸带上写1B　　C0后移A　　…………　　因此，图灵机只要根据每一时刻读写头读到的信息和当前的内部状态进行查表就可以确定它下一时刻的内部状态和输出动作了。　　图灵机就是这么简单！不可思议吧？而只要你变化它的程序（也就是上面的规则表），那么它就可能为你做任何计算机能够完成的工作

4、。因此可以说，图灵机就是一个最简单的计算机模型！　　也许，你会觉得图灵机模型太简单，怎么可能完成计算机的复杂任务呢？问题的关键是如何理解这个模型。