什么是图灵机?

[拼音]：Tulingji

[外文]：Turing machine

英国数学家A.M.图灵于1936年提出的一种抽象自动机，用来定义可计算函数类。在数学上递归函数和λ可定义函数均等价于图灵机定义的可计算函数。图灵机能表示算法、程序和符号行的变换，因而可作为电子计算机的数学模型，也可用作控制算法的数学模型，在形式语言理论中还可用来研究短语结构语言（即递归可数语言）。40年代以来，许多科学家根据图灵的构思提出了一系列抽象自动机，来研究神经网络和各种高级控制系统（如自适应、自学习、自组织、自繁殖等系统）。

图灵机由控制器、存储带和读写头组成。

（1）控制器：它是一台时序机，即有限自动机，具有有限个内在状态，包括初始状态和终止状态。控制器内存有 *** 作程序，即指令序列，用来驱动存储带左右移动和控制读写头的 *** 作。

（2）存储带：它是一条可向两端无限延伸的带子，带上分成一个个方格，每一方格可以存储规定字符表中的一个字符，也可保持空白。

（3）读写头：它能与存储带进行相对运动，并对存储带进行扫描，每次读出或写入一个字符。读写头与控制器能进行双向通信，即接受控制器的指令，并将扫描结果送到控制器。图中示出图灵机的构造。

图灵机可用一个三元组(W，p，s)表示，式中W是存储带上的符号串；p表示读写头与存储带的相对运动；s是图灵机的内在状态。因此,图灵机在某一时刻的形象即格局可描绘成下列形式

这里C1C2…Cm是存储带上的符号串,读写头正扫描Cj,当时图灵机的内在状态是Si。图灵机的计算就是形象变化过程。如果把内在状态看作符号行的一部分，即把内在状态嵌入形象符号串中，则图灵机的计算就是一种符号行的变换。

图灵机的程序可用程序表来说明，此时要区别主动状态和被动状态。图灵机处于主动状态就继续执行，处于被动状态就停机。如果图灵机有n个内在状态和由m个符号构成的符号表,则可用n×(m＋1)的表格来表示它的程序。表中每一元素就是一条指令，每条指令有运算指令和转移指令两部分，图灵机的内在状态起着指令标号的作用。例如,元素Ckpsl表示把读写头扫描的方格改写成符号Ck，根据p 的取值使存储带右移一格，或左移一格,或保持不动,图灵机转到内在状态sl。如果图灵机当前处于内在状态si,读写头正在扫描字符Cj,则图灵机的指令可写成siCjCkpsl。其中si∈{s1,s2,…,sn},Cj∈{C1,C2,…,Cm},p∈{r，l，h},这里r表示右移一格，l表示左移一格，h表示不动。

图灵机有两种基本功能：

（1）作为函数计算机，它能计算一切可计算函数。例如，如果图灵机的存储带上输入符号串为n的编码,经过有限步 *** 作后存储带上的符号串变为m的编码，则称该图灵机计算了函数 f(n)＝m 。

（2）作为语言识别器，它能识别0型语言,即递归可枚举集(见短语结构文法）。

1936年图灵提出可构造一种通用图灵机U来模拟其他图灵机T的计算。如果 U的存储带上存有表征T的形象的符号串，则U将在带上写入 T在计算中得到的各种情况。因此读写头扫描U带上的内容即可获得T带上的内容。这就表明可用通用图灵机来模拟任何其他的图灵机。1956年C.E.香农证明了可构造只有两个内在状态的通用图灵机。通用图灵机的概念与通用电子数字计算机的概念等价。通用电子数字计算机是输入程序和数据,然后按程序进行计算。计算的种类由程序决定,不由计算机决定。通用图灵机U也是这样，输入的是数组(t，x),这里t是图灵机T的哥德尔数，即T的程序，x是输入数据。U对于这个数组的计算与T对x的计算等价,所以只要对U输入T的程序,U即可进行T的计算。1945年J.von诺伊曼根据通用图灵机的概念提出存储程序式电子数字计算机方案。

1960年德国数学家S.C.克林提出广义图灵机，用以定义部分递归的有限元泛函。克林提出的广义图灵机是一种具有解算装置的完整的计算过程。解算装置可看作是图灵机的一条辅助带，它的内容可复制到主带上来，从而扩大图灵机的计算能力。这种图灵机定义的可计算函数是相对递归函数。

任何改进型图灵机的计算能力均与图灵机等价，改进的目的是为了提高计算效率，寻找新的数学模型，以便于研究各种不同类型的信息处理问题。例如，多带图灵机可作为研究计算复杂性理论的数学模型。图灵机的改进主要有以下两个方面：

（1）计算方式:图灵机的计算方式极为原始，为了改进这种情况，可增加读写头和存储带的数目，甚至把一维带变成多维带。这样做相当于在计算机中增加寄存器和存储器，增加平行处理功能。

（2）指令形式:可采用没有内在状态的机器,使图灵机的指令形式更接近于现代计算机。1936年英国数学家E.L.波斯特提出的波斯特机就是这样的机器，它采用符号集{0,1},比图灵机更接近现代计算机。1957年美籍数学家王浩提出的W机，它的构思与波斯特机相同,但程序更为简洁。改进型图灵机还有许多型式，各有不同的用处。如半无限带图灵机、多头图灵机、多带图灵机、多维图灵机、无限多寄存器机器 （即URM机）和明斯基机等。

图灵机根据程序处理初始格局，有的导致停机,有的导致无限格局序列。人们就提出,是否存在一个算法，能判定任意给定的图灵机对任意的初始格局是否会导致停机。这就是著名的图灵机停机问题。已经证明,这样的算法是不存在的,即停机问题是不可判定的。人们往往把一个问题的判定归结为停机问题，所以停机问题是研究不可判定问题的基础。

参考书目

申南和麦克卡赛编,陈中基编译：《自动机研究》,科学出版社,北京,1963。(C.E.Shannon and J. McCarthy (eds)，Automata Studies， Princeton University Press, Princeton, N.J.,1956.)