Question

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

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

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

或许不足为奇的是，一台图灵机足够强大，它能从纸带读取一台简单机器的描述——比如说，一台确定性有限自动机——然后运行这台机器的模拟以找出它的工作内容。在3.1.4节，我们根据描述写下Ruby 代码来模拟一台DFA，现在只需要一点点工作就可以把那个代码的思想转化成一台图灵机的规则手册，以运行同样的模拟。

能模拟一台特定DFA 的图灵机和一台能模拟任何DFA 的图灵机有着重要的区别。

设计一台图灵机重现一台特定DFA 的行为很简单——毕竟，一台图灵机只不过是一台装有纸带的确定性有限自动机。DFA 规则手册的每一条规则都可以直接转成一个等价的图灵机规则；每一个转换过来的规则不是从DFA 的外部输入流中读取，而是从纸带读取一个字符，并把纸带头移动到下一个方格。但这不是特别有趣，因为得到的图灵机并不比原始的DFA 有用。

更有趣的是模拟通用DFA 的图灵机。这样的机器可以从纸带读取一个DFA的设计——规则、起始状态以及接受状态——然后遍历那台DFA 执行的每一步，同时使用另一部分纸带跟踪模拟机器的当前状态和剩余的输入。通用模拟实现起来要难得多，但它让我们只要提供DFA 的描述作为输入，就可以让图灵机做一台DFA 能做的任何工作。

这也适用于对NFA、DPDA 和NPDA 的Ruby 模拟，它们都可以转换成能模拟那种类型的任意自动机的一台图灵机。但关键是，对我们图灵机模拟本身，它也能起作用：通过把Tape、TMRule、DTMRulebook 以及DTM 重新实现成图灵机的规则，我们能设计一台图灵机，它能通过从纸带读取其规则、接受状态以及起始配置然后单步执行，模拟任何其他确定型图灵机，本质上这扮演着图灵机规则手册解释器的角色。完成这种工作的机器叫作通用图灵机（Universal Turing Machine，UTM）。

这非常激动人心，因为它在一个可编程装置中使图灵机的最大计算能力变得可用。我们可以把软件——经过编码的图灵机描述——写到纸带上，把这个纸带提供给UTM，然后执行软件产生想要的行为。有限自动机和下推自动机不能用这种方式模拟它们自身的类型，因此图灵机不只标志着从能力有限的计算机器到能力强大的计算机器的过渡，还标志着从单用途设备到全编程设备的转变。

简单地看一下一台通用图灵机如何工作。在实际构建一台UTM 时，涉及大量的技巧和无趣的技术细节，因此我们的探索将会相当肤浅，但至少应该能证明这样的事情是可能的。

5.4.1　编码

在设计一台UTM 的规则手册之前，我们得决定如何把一台完整的图灵机表示成纸带上的一个字符序列。一台UTM 需要读取任意图灵机的规则、接受状态以及起始配置，然后随着模拟的进程，不断更新模拟机器的当前配置，因此我们需要一个实用的方式存储这些信息，以便UTM 能与其协同工作。

有一个挑战，即每一台图灵机都只能在它的纸带上存储有限数目的状态和有限数目的不同字符，这两个数都由它的规则手册预先固定好了，当然UTM 也不例外。如果我们设计一台UTM，它能处理10 个不同的纸带字符，那它如何模拟一台规则里使用11 个字符的机器呢？如果我们更慷慨一些，让它能处理100 个不同的字符，那么当想要模拟使用1000个字符的机器时会发生什么呢？不管我们为UTM 自己的纸带设计多少个字符，为了直接表示每一个可能的图灵机它总是不够用的。

在所模拟机器和UTM 之间还会有字符冲突的风险。为了在纸带上存储图灵机的规则和配置，我们需要能够用在UTM 中有特殊含义的字符标注它们的边界，以便它能告诉我们从哪儿开始一个规则结束了，另一个规则开始了。但如果我们选择X 作为规则之间的特定标识，则只要所模拟的任何一条规则中含有字符X，都会有问题。即使我们设置一个保留字符的超级特殊集合，只给一台通用图灵机使用，如果试图模拟这台UTM 本身的话仍然会引起问题，因此机器不会是真正通用的。这表明，我们需要某种转义，以避免所模拟机器的普通字符被UTM 错误地解释成特殊字符。

我们可以解决这两个问题，方法是对所模拟机器的纸带内容使用固定指令系统的字符进行编码。如果编码体系只使用了特定的字符，那么我们可以保证对UTM 来说把其他字符做特殊目的使用是安全的，而且如果这个体系能容纳任意数目的模拟状态和模拟字符，那就没有必要担心所模拟机器的规模和复杂度了。

只要能实现这些目标，这个编码体系的具体细节并不重要。举个例子，一个可能的方法是使用一元5表示法把不同的值编码成同一字符重复不同次数的字符串：如果所模拟机器使用字符a、b 和c，它们可以编码成1、11 和111。另一个字符，如0，可以用来作为值的分界标识：字符串abc 可以标识成101110110111。这种方法在空间上效率不是很高，但它可以通过在纸带上存储越来越长的由1 组成的字符串来进行扩展，以容纳任意数目的编码的字符。

5二元基于2，一元基于1。

一旦决定了如何对单个字符进行编码，我们就需要一种描述所模拟机器规则的方法。可以通过对规则的各个部分（状态、字符、下一状态、要写入的字符、移动方向）进行编码来实现，然后把它们在纸带上连接在一起，并在必要的地方使用特殊的分隔符。在示例的编码系统里，我们也可以用一元法表示状态——状态1 是1，状态2 是11，以此类推。但既然知道只会有两个方向，那我们可以使用任意的专用字符表示左和右（比如说L 和R）。

我们可以把单个的规则连到一起表示整个规则手册。类似地，可以通过把它当前状态的表示和它当前纸带内容的表示连在一起，来对所模拟机器的当前配置进行编码。6 而且这给了我们想要的：一台完整的图灵机以字符串的形式写在另一台图灵机的纸带上，准备通过模拟开始自己的生命周期。

6我们没有详细说明纸带应该如何表示，但这也不难，而且总是可以选用5.3.3 节的多纸带技术把它存储到所模拟的从纸带上。

5.4.2　模拟

从根本上说，通用图灵机和我们在5.1.4 节构建的Ruby 模拟的工作方式一样，只是要费力得多。

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

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