图灵机

出处：按学科分类—自然科学总论 天津人民出版社《自然辩证法辞典》第500页（456字）

一种抽象机器。

英国计算机科学家图灵在1936年提出了一种描述计算过程的数学模型，后来人们就称这个数学模型为图灵机。图灵机被用来讨论“可计算”问题，从而得到了一个叫做图灵论题的定义：所有能称为“可计算”的函数恰恰就是用图灵机可计算的函数。这是一个既不能证明，又无法否定的论题。它实际上已为广大的计算机科学家所接受，并且人们证明了以下事实：图灵机可计算的函数类恰恰是一般递归函数类。

图灵机由一个控制部件、一条存贮带和一个读写头构成的。这种机器所能进行的操作为：(1)左移(读写头在存储带上向左移一格)；(2)右移(读写头向右移一格)；(3)在存贮带的某一格内写下或清除一个符号；(4)条件转移。

图灵机的结构虽比较简单，但在理论上它却能够模拟现代数字计算机的一切运算，因之可以看作是现代数字计算机的一种数学模型，可通过对这种模型的研究来揭示数字计算机的性质。但这种机器在用作现代计算机的模型时，是有局限性的。后来有人提出改进的图灵机(例如多带图灵机)可能会更合适一些。