图灵机

出处：按学科分类—自然科学总论 山东人民出版社《方法大辞典》第123页（810字）

一种定义算法的理想机器。

由英国数学家图灵在1936年定义的。1939年他又将图灵机的概念进行了推广。

图灵机是图灵提出的一种自动机的抽象路线，是描述现代数字计算机的基本行为的模型。这种自动机在原则上适于实现任何算法。由三个基本部分组成：一是控制部件，二是读写头，三是一条无限长的存贮带。因该存贮带有开端而无结尾，所以图灵机是一种无限记忆的自动机。

控制部件是一台时序机，它有一个驱动系统，这个驱动系统能在两个方向上移动存贮带。存贮带可以设想为是任何一种能够存贮，阅读和修改信息的外部介质。

存贮带被划分成一个个的方格，每个方格或者包含一个不记录数据的空白，或者包含属于有限符号集A的一个符号。读写头一次只能扫描一个方格。图灵机的运行是这样的：准备一条存贮带，将数据符号设置在带上的相应方格中，时序机进入起始状态，再把所准备的存贮带装在机器上，并使相应方块位于读写头下，然后开机。在这里需要指出的是，图灵机只是现代数学计算机的基本行为的描述性模型，在实际上使用按图灵原理作出的自动机是不现实的，因为解决非常复杂的问题所需要进行的步数太多，这就意味着解决一个问题需要很长的解题时间。

尽管如此，图灵机理论对于某一类问题的解的算法存在性问题是很重要的，因为它可以指明什么功能是能自动完成的，什么功能是不能自动完成的，特别是用象数字计算机这样的通用自动机。

图灵机分为特定图灵机和通用图灵机。特定图灵机是通过机器的控制部件所安排的步骤来计算给定函数的。通用图灵机则用来解释存贮带表达式，然后执行适当的计算过程。

这种通用图灵机是一种能模拟任何特定图灵机的图灵机。任何特定图灵机所能完成的任何计算，通过适当的编码方法，通用图灵机都能完成。

通用图灵机的使用过程与常规存贮程序数字计算机并无差别，主要不同点在于通用图灵机具有一条潜力无限的存贮带。