有限自动机和下推自动机——都有很严格的限制，这些限制影响了它们作为现实计算模型的使用。我们的小型系统还要多强大，才能摆脱这些限制并完成正常计算机的所有工作呢？它还要多复杂才能对 RAM 或硬盘的行为以及合适的输出机制建模呢？怎么才能设计一台能实际运行程序而不总是执行某个硬编码任务的机器呢？

20 世纪 30 年代，阿兰·图灵（Alan Turing）致力于从本质上解决这个问题。在那个年代，单词 computer 意味着一个人，通常是一个女人，她手工重复着一系列繁重的数学性操作以执行长长的计算。图灵当时正在寻找一种理解和描述“人肉计算机”操作特征的方法，这样同样的工作就可以完全由机器执行。本章，我们将看到图灵关于设计最简单的“自动化机器”的思想，这一机器具有手工计算的全部能力和复杂性。

确定型图灵机

我们通过给一台有限自动机赋予一个作为外部存储的栈，增强了它的计算能力。与由机器状态提供的有限内部存储相比，栈的真正优点是能动态增长以适应任意数量的信息，从而使下推自动机能够处理那些需要存储任意数量数据的问题。

但是，外部存储这种特殊的形式给如何使用存储之后的数据带来了限制。通过把栈替换成更灵活的存储机制，我们可以消除这些限制并进一步提高能力。

存储

计算通常可以通过在纸上写某些符号完成。我们可以把这张纸想象成小朋友的算术本，它被划分成了一个个方格。在初等算术里，我们有时也会使用纸的二维特性。但这种使用通常是可以避免的，并且我认为纸的二维性不是计算的本质，而且相信大家也赞同我这一观点。我假定计算是在一张一维的纸上完成的，比如在一条分成方格的纸带上完成。 ——阿兰•图灵， 《论可计算数及其在判定性问题上的应用》

图灵的做法是给一台机器配上一条无限长的空纸带（实际上是一个两端都能随需增长的一维数组） ，并且允许在纸带上的任意位置读写字符。一条纸带既做存储又做输入：可以在纸带上预先填满字符串当作输入，然后机器在执行过程中可以读取这些字符并在必要的时候覆盖它们。

能访问一条无限长纸带的有限状态自动机叫作图灵机（Turing Machine，TM ） 。这个名字通常指一条拥有确定性规则的机器，但我们也可以毫无歧义地叫它确定型图灵机（Deterministic Turing Machine，DTM） 。

传统的图灵机使用简单的安排：用一个纸带头（tape head）指向纸带的一个特定位置，并且只能在那个位置读取或写入字符。每一步计算之后，纸带头都可以向左或者向右移动一个方格，这意味着一台图灵机为了到达远处的位置只能费力地在纸带上往复移动。使用移动缓慢的纸带头不会影响机器访问纸带上任何数据的能力，只会影响花费的时间，因此为了保持简单付出这个代价是值得的。

能访问纸带之后，除了能够接受或者拒绝字符串，我们又能解决新的问题了。例如，我们可以设计一台在纸带上就地递增一个二进制数的 DTM。为此，我们需要知道如何递增一个二进制数的一位数字。幸好这很简单：如果这位的数字是 0，就用 1 替换；如果这位数是 1，就用 0 替换，然后立即使用同样的方法增加它左边的数字（ “进 1 位” ） 。图灵机只需要使用这个过程递增二进制数的最右位，然后把纸带头移到起始位置。

  • 给机器赋予三个状态（状态 1、状态 2、状态 3） ，状态 3 作为接受状态
  • 机器从状态 1 开始，纸带头指向一个二进制数的最右位
  • 处于状态 1 并且读到一个 0（或者空白）时，就用 1 覆写，把纸带头向右移，然后回到 状态 2
  • 处于状态 1 并且读到一个 1 时，就用 0 覆写，然后把纸带头向左移
  • 处于状态 2 并且读到一个 0 或者 1 时，就把纸带头向右移
  • 处于状态 2 并且读到空白时，就把纸带头向左移并转移到状态 3

在机器试图递增一位数字的时候，它处于状态 1，在移回起始位置时处于状态 2，结束的时候处于状态 3。下面是初始纸带上字符串为 ‘1011’ 时对机器执行的跟踪。纸带头当前指向的字符会由括号包围，而下划线表示输入字符串某一端的空白方格。

规则

让我们想象一下，由机器执行的操作被分解成“简单的操作” ，这些操作都非常基本，以至于无法想象它们能进一步分解。……操作实际上是由计算者的思维状态和被观察的符号决定的……具体来讲，操作执行之后，计算者的思维状态就确定了。
我们现在可以构造一台做这种计算者工作的机器了。 ——阿兰•图灵， 《论可计算数及其在判定性问题上的应用》

在每一步计算中，可能都有几个“简单的操作”需要图灵机执行：在纸带头的当前位置读取字符，在那个位置写入一个新字符，把纸带头左移或者右移，或者改变状态。简单起见，我们没有为所有这些动作指定不同种类的规则，而只是像处理下推自动机时那样，只设计了一种能灵活适应各种条件的规则格式。

这个统一的规则格式有 5 部分：

  • 机器的当前状态
  • 必须出现在纸带头当前位置的字符
  • 机器的下一状态
  • 要写入纸带头当前位置的字符
  • 写入纸带之后纸带头的移动方向（向左还是向右）

这里我们假设一台图灵机每次执行规则，都要改变状态并向纸带写一个字符。就像通常对状态机的处理那样，如果我们想要一个规则不实际改变状态，可以让“下一个状态”与当前状态相同；与之类似的是，如果想要一个规则不改变纸带内容，可以把与读到的字符一样的字符写入纸带。

非确定性图灵机

我们看到非确定性没有让有限自动机有什么不同。增加不确定性不会使一台图灵机更加强大。因为 DFA 和 DTM 都有足够的能力模拟其非确定性的对应机器。

最大能力

确定型图灵机代表了从有限计算机器到全能机器的临界点。实际上，通过升级图灵机规范以使其更强大的任何尝试都注定失败，因为它们本来就有能力模拟任何潜在的增强了。尽管增加某些特性会使图灵机更小巧或者更高效，但无法从根本上增强它们的能力。

例如对传统图灵机的 4 个其他扩展——内部存储、子例程、多纸带以及多维纸带，没有任何一个可以增加计算能力。

通用机器

尽管到目前为止我们看到的机器都有严重的缺陷：它们的规则都是硬编码的，这让它们无法适应不同的任务。一台能接受与一个特定正则表达式匹配的字符串的 DFA，不可能学会接受一个不同集合的字符串；一台能识别回文的 NPDA 将只能识别回文；一台递增二进制数的图灵机将永远不能做其他用途。

大多数现实中的计算机不是这么工作的。现代计算机不是专门做某一项特殊工作的，而是为了通用目的而设计的并且能通过编程执行不同的任务。尽管一台可编程计算机的指令集和 CPU 设计是固定的，但能通过软件控制它的硬件并根据用户需要改变它的行为。

我们的简单机器能做这样的事情吗？在做一件不同的工作时，不必每次去设计一台新的机器，而是设计一台简单机器，它会从输入读取一个程序，然后做这个程序定义的任何工作。这办得到吗？

或许不足为奇的是，一台图灵机足够强大，它能从纸带读取一台简单机器的描述——比如说，一台确定性有限自动机——然后运行这台机器的模拟以找出它的工作内容。

一台完整的图灵机以字符串的形式写在另一台图灵机的纸带上，准备通过模拟开始自己的生命周期。

它的规则手册、接受状态以及起始配置——都以编码的格式存在于UTM 的纸带上。为了执行模拟的一步，UTM 要在规则、当前状态和所模拟机器的纸带之间来回移动纸带头，以搜索出能应用到当前配置的一条规则。它找到一条规则的时候，就会根据规则里定义的字符和方向，更新所模拟的纸带，并把所模拟的机器放到新的状态上去。

这个过程会一直重复，直到所模拟的机器进入到一个接受状态，或者到达某个配置后因为没有规则应用处于卡死的状态。