图灵机由一条无限长的纸带和一个什么组成

发布网友发布时间：2023-01-05 00:54

共1个回答

热心网友时间：2023-01-25 10:14

图灵机由一条无限长的纸带和一个读写头 HEAD、一套控制规则 TABLE 以及一个状态寄存器组成，具体如下：

为了模拟人的这种运算过程，图灵构造出一台假想的机器，该机器由以下几个部分组成：

1、一条无限长的纸带 TAPE。纸带被划分为一个接一个的小格子，每个格子上包含一个来自有限字母表的符号，字母表中有一个特殊的符号表示空白。纸带上的格子从左到右依此被编号为0，1，2，…，纸带的右端可以无限伸展。

2、一个读写头 HEAD。该读写头可以在纸带上左右移动，它能读出当前所指的格子上的符号，并能改变当前格子上的符号。

3、一套控制规则 TABLE。它根据当前机器所处的状态以及当前读写头所指的格子上的符号来确定读写头下一步的动作，并改变状态寄存器的值，令机器进入一个新的状态。

4、一个状态寄存器。它用来保存图灵机当前所处的状态。图灵机的所有可能状态的数目是有限的，并且有一个特殊的状态，称为停机状态。参见停机问题。

图灵提出图灵机的模型并不是为了同时给出计算机的设计，它的意义有如下几点：

（1）它证明了通用计算理论，肯定了计算机实现的可能性，同时它给出了计算机应有的主要架构。

（2）图灵机模型引入了读写与算法与程序语言的概念，极大的突破了过去的计算机器的设计理念。

（3）图灵机模型理论是计算学科最核心的理论，因为计算机的极限计算能力就是通用图灵机的计算能力，很多问题可以转化到图灵机这个简单的模型来考虑。

以上内容参考：百度百科-图灵机