1.2 图灵机模型

首先了解一下图灵。艾伦·麦席森·图灵（Turing Alan Mathison），1912年生于英国伦敦，1954年逝于英国的曼彻斯特，被誉为计算机科学之父、人工智能之父，如图1-1所示。为纪念图灵在计算机领域的卓越贡献，美国计算机协会（Association of Computing Machinery，ACM）自1966年起设置了“图灵奖”。该奖项用以表彰在计算机科学中做出突出贡献的人。图灵对现代计算机的贡献主要是：建立了图灵机的理论模型，发展了可计算性理论，并提出了定义机器智能的图灵测试。

图1-1 艾伦·麦席森·图灵

下面通过图灵机的组成及其基本思想，认识、理解图灵机模型与现代计算机的关系。

1936年，图灵在可计算性理论的研究中，提出了一种抽象的计算机模型——图灵机（Turing Machine）。该机器由以下几部分组成。

1. 一条无限长的纸带

纸带自左至右被划分为一个连一个的格子，每个格子都有相应的编号，并且纸带的右端可根据需要无限延伸，而纸带上的格子可以用于书写符号和运算。

2. 一个读写头

读写头能够读取纸带上某一方格内的信息，并能够在当前格子上书写、修改或擦除数据。

3. 一套控制规则

根据当前读写头所指的格子上的符号和机器的当前状态来确定读写头下一步的动作，并改变状态寄存器的值，令机器进入一个新的状态。

4. 一个状态寄存器

用来保存图灵机当前所处的状态。图灵机所有可能的状态的数目是有限的，其中停机状态是一种特殊状态。

图灵机不是具体的机器，而是一种思想模型，可制造十分简单但运算能力极强的计算装置。该装置可用来计算所有能想象得到的可计算函数。图灵的基本思想是用机器来模拟人们用纸笔进行数学运算的过程。

图灵机被公认为现代计算机的原型，可以读入一系列的0和1。这些数字代表了解决某一问题所需要的步骤，按步骤走下去，就可以解决某一特定的问题。图灵机只用保留一些最简单的指令，而困难的是，如何确定最简单的指令集，怎么样的指令集才是最少的，而且又能顶用，还有一个难点是如何将复杂问题分解为简单指令。

可用一个图灵机来计算其值的函数是可计算函数，找不到图灵机来计算其值的函数是不可计算函数。可以证明，存在一个可以模拟任何其他的图灵机的图灵机U，这样的图灵机U称为通用图灵机。在给出通用图灵机的同时，图灵就指出，通用图灵机在计算时，其“机械性的复杂性”是有临界限度的，超过这一限度，就要靠增加程序的长度和存贮量来解决。这种思想开启了后来计算机科学中计算复杂性理论的先河。

总之，图灵机反映的是一种具有能行性的、用数学方法精确定义的计算模型。该计算模型的目标就是要建立一台可以计算的机器，也就是将计算自动化。而现代计算机正是这种模型的具体体现。