什么是图灵机?

什么是图灵机?

[拼音]：Tulingji

[外文]：Turing machine

英国数学家A.M.图灵提出的一种抽象计算模型，用来精确定义可计算函数。图灵机由一个控制器、一条可无限延伸的带子和一个在带子上左右移动的读写头组成。这个在概念上如此简单的机器，理论上却可以计算任何直观可计算的函数。图灵机作为计算机的理论模型，在有关计算理论和计算复杂性的研究方面得到广泛的应用。

研究简况

由于图灵机以简明直观的数学概念刻划了计算过程的本质，自1936年提出以来，有关学者对它进行了广泛的研究。C.E.仙农证明每一个图灵机等价于仅有两个内部状态的图灵机，王浩证明每个图灵机可由具有一条只读带和一条只有两个符号的存储带的图灵机模拟。人们还证明，图灵机与另一抽象计算模型──波斯特机器在计算能力上是等价的（见波斯特对应问题）。

人们还研究了图灵机的各种变形，如非确定的图灵机、多道图灵机、多带图灵机、多维图灵机、多头图灵机和带外部信息源的图灵机等。除极个别情形外，这些变形并未扩展图灵机的计算能力，它们计算的函数类与基本图灵机是相同的，但对研究不同类型的问题提供了方便的理论模型。例如，多带图灵机是研究计算复杂性理论的重要计算模型。人们还在图灵机的基础上提出了不同程度地近似于现代计算机的抽象机器，如具有随机访问存储器的程序机器等。

基本结构和功能

图灵机（见图）的控制器具有有限个状态。其中有两类特殊状态：开始状态和结束状态（或结束状态集合）。图灵机的带子分成格子，右端可无限延伸，每个格子上可以写一个符号，图灵机有有限个不同的符号。图灵机的读写头可以沿着带子左右移动，既可扫描符号，也可写下符号。

在计算过程的每一时刻，图灵机处于某个状态，通过读写头注视带子某一格子上的符号。根据当前时刻的状态和注视的符号，机器执行下列动作：转入新的状态；把被注视的符号换成新的符号；读写头向左或向右移动一格。这种由状态和符号对偶决定的动作组合称为指令。例如指令q1ai│ajq2L表示当机器处在状态q1下注视符号ai时，将ai换成符号aj，转入新的状态q2，读写头左移一格。决定机器动作的所有指令表称为程序。结束状态或指令表中没有的状态、符号对偶，将导致停机。

在每一时刻，机器所处状态、带子上已被写上符号的所有格子以及机器当前注视的格子位置，统称为机器的格局。图灵机从初始格局出发，按程序一步步把初始格局改造为格局的序列。此过程可能无限制继续下去，也可能遇到指令表中没有列出的状态、符号组合或进入结束状态而停机。在结束状态下停机所达到的格局是最终格局，此最终格局(如果存在)就包含机器的计算结果。

图灵机接受语言

图灵机（简记为 T）可作为接受语言的装置，它所接受的语言L恰是所有这样的符号串ω的集合：如果把符号串ω记录在T的带子上，开始工作时T处于初始状态q0，读写头处于带子最左端，则经过有限步之后，T进入某个结束状态q。被图灵机接受的语言类也就是递归可枚举集，或 O型语言（见形式语言理论）。

图灵机产生语言

图灵机作为语言的产生装置，它在带子上枚举出该语言中所有的字。如果这个语言是无限的，这个枚举过程就是无穷的。图灵机产生的语言恰是递归可枚举集。图灵机按字长增长的顺序产生的语言，恰是递归集。

图灵机计算函数

设机器带子上的输入符号串为自然数n的编码。如果机器从这样的带子出发，到达结束状态时，带子上符号串已改造为m的编码，则称机器计算了函数f(n)=m。如果一个函数以自然数为值域和定义域，并且有一个图灵机计算它，则称此函数为“可计算函数“。

由于图灵机的带子是可以向右无限延伸的，所以图灵机的存储空间和计算时间都是可无限制增加的。因此，图灵机是一般算法概念的精确化，即任何算法均可由适当的图灵机模拟。人们尚未发现一个直观可以计算的函数不能由图灵机来计算。而且，已有的关于直观可计算函数的另一些精确化定义，如递归函数、λ 可定义函数等，都等价于图灵机定义的可计算函数。

通用图灵机

已经证明，存在一个图灵机U，它可以模拟任何其他的图灵机T，这样的U称为通用图灵机。U的带子上记录着被模拟机器T的指令描述，也记录着T的问题数据。在工作过程中，U根据输入带上记录的T的指令，模拟T的动作，处理问题的数据。这样，U可以模拟任何计算过程。

停机问题

图灵机根据机器的程序处理初始格局。有的初始格局可能导致停机，有的则导致无限的格局序列。停机问题是：是否存在一个算法，对于任意给定的图灵机都能判定任意的初始格局是否会导致停机。已经证明，这样的算法是不存在的，即停机问题是不可判定的。

停机问题是研究许多不可判定问题的基础，人们往往把一个问题的判定归结为停机问题：“如果问题 A可判定，则停机问题可判定。”从而证明问题 A的不可判定性。停机问题有多种不同的叙述方式和证明方法，它们分别适用于具有不同特征的问题。

参考书目

M.Davis，Computability and Unsolvability，McGraw-Hill， New York， 1958.