计算机科学导论：跨学科方法

5.2　图灵机

艾伦·图灵在1937年发表的论文中介绍了20世纪最美丽而有趣的知识发现之一，这是一个简单的计算模型，它足以体现任何计算机程序的特征，并且构成了计算机理论的基础。因为它的描述和行为都很简单，所有我们可以很容易地对它进行数学分析。这个分析让图灵对计算机和计算有了更深入的理解：所有已知的计算设备从深层次的技术原理层面来说都是等价的，而且有一些计算问题无论处理器有多快或者有多少可用的内存，都是根本无法解决的。我们会在接下来的两节中讨论这些想法，作为基础，我们首先需要分析图灵的发明到底是什么，以及它的概念和基本属性是什么。

如果你在其他地方曾经阅读过有关图灵机的资料，或者将来在其他材料中遇到图灵机，你会发现它的定义和某些属性与我们给出的略有不同。事实上这种差距是无关紧要的，这个理论中关键的一点就是，我们创造的任何计算模型都可以变形为与之等价的复杂模型。我们使用的方法是根据20世纪中叶麻省理工学院的马文·明斯基开发的一个模型改编的。

图灵机模型　我们研究的目标是一个抽象的机器模型，它比前一部分所提到的DFA模型要稍微复杂一些，这个模型被称为图灵机（Turing Machine，TM）。在下面的描述中，我们会将它与图灵机的区别用蓝色明显地标识出来。每个TM由以下部分组成：

·有限数量的状态，每个状态都被设定成左状态、右状态、暂停状态、接受状态和拒绝状态中的一个。

·一组用于指定下一个状态以及要写入哪个符号的迁移。每个状态对于符号表中的每个符号都有一个迁移。

·一个存有符号字符串的纸带。

·一个能够读或写一个符号并且能够向左或向右移动来读取下一个符号的纸带头。

一个TM操作从状态0开始，而且此时纸带头的位置在输入符号的第一个（最左侧），然后读取和写入纸带并根据以下规则按照步骤改变状态： ...