Question

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

3严格来讲，只有我们实际知道如何实现的增强才算数。如果赋予一台图灵机魔力，让它能立即推理出传统图灵机无法回答的问题的答案，它确实会变得更强大，但实际上，这是无法做到的。

我们之前已经看到了对于非确定性来说为什么这是对的。现在来看一下对传统图灵机的 4 个其他扩展——内部存储、子例程、多纸带以及多维纸带——并领会为什么它们中没有一个可以增强计算能力。尽管涉及的模拟技术很复杂，但到最后，它们都只不过是编程方面的问题。

5.3.1　内部存储

为图灵机设计规则手册非常让人沮丧，因为它们缺少随机的内部存储。例如，我们经常想要机器把纸带头移动到一个特定的位置，读取存在那儿的字符，然后移动到另一个不同的部分，再根据之前读到的字符执行某个动作。表面看来，这似乎不太可能，因为没有地方能让机器“记住”那个字符——当然它仍旧写在纸带上，并且只要我们喜欢，就可以把纸带头移动回到那里再次对其读取，但只要纸带头从那个方格移开了，我们就再也不能根据它的内容触发一个规则了。

如果图灵机有一些临时性的内部存储（可以叫它“RAM”“寄存器”“本地变量”，等等）会更方便，其中可以保存纸带当前方格的字符，而且即使以后纸带头已经完全移动到了不同的部分，也能对其引用。实际上，如果一台图灵机有这个能力，我们就没必要限制它存储纸带上的字符：它可以存储任何相关的信息，比如机器执行计算的中间结果，从而把我们从来回移动纸带头向纸带写回碎片数据的繁琐工作中解放出来。这个额外的灵活性好像能让图灵机执行新类型的任务了。

就像非确定性一样，为图灵机增加额外的内部存储确实会让某些任务更容易执行，但它并不能让机器做任何它本来不能完成的工作。把中间结果存在机器内部而不是纸带上的念头很容易消除，因为即使让纸带头来回移动访问这些信息要花费些工夫，用纸带存储这种信息也能工作得很好。但我们不得不更加认真地看待这个记忆字符的点，因为如果纸带头移动到其他地方之后就不能利用之前纸带方格里的内容的话，一台图灵机的作用会非常有限。

幸好图灵机有非常完美的内部存储——它的当前状态。图灵机可用的状态数目没有上限，但对于任意的特定规则集合来说，这个数目一定是有限的并且要预先决定好，因为无法在计算过程中创建新的状态。如果必要，我们可以设计一台拥有100 个、1000 个，甚至10亿个状态的机器，然后使用当前状态记住从一步到下一步任意数量的信息。

这意味着免不了要复制规则适应多个状态，因为这些状态除了“记住”的信息不同外都是相同的。一台机器不是只用一个状态表示“向右扫描查找一个空白方格”，而是可以为“向右扫描查找一个空白方格（记住我之前读取到了一个a）”设置一个状态，再为“向右扫描查找一个空白方格（记住我之前读取到了一个b）”设置另一个状态，所有可能的字符都以此类推——字符数目也是有限的，所以这样的复制总是有限的。

下面是一个使用这种技术的图灵机，它会把一个字符从字符串的开头复制到结尾：

>> rulebook = DTMRulebook.new([
    # 状态 1： 从磁带读取第一个字符
    TMRule.new(1, 'a', 2, 'a', :right), # 记住 a
    TMRule.new(1, 'b', 3, 'b', :right), # 记住 b
    TMRule.new(1, 'c', 4, 'c', :right), # 记住 c

    # 状态 2： 向右扫描，查找字符串结束标记（记住 a）
    TMRule.new(2, 'a', 2, 'a', :right), # 跳过 a
    TMRule.new(2, 'b', 2, 'b', :right), # 跳过 b
    TMRule.new(2, 'c', 2, 'c', :right), # 跳过 c
    TMRule.new(2, '_', 5, 'a', :right), # 找到空格，写 a

    # 状态 3： 向右扫描，查找字符串结束标记（记住 b）
    TMRule.new(3, 'a', 3, 'a', :right), # 跳过 a
    TMRule.new(3, 'b', 3, 'b', :right), # 跳过 b
    TMRule.new(3, 'c', 3, 'c', :right), # 跳过 c
    TMRule.new(3, '_', 5, 'b', :right), # 找到空格，写 b

    # 状态 4： 向右扫描，查找字符串结束标记（记住 c）
    TMRule.new(4, 'a', 4, 'a', :right), # 跳过 a
    TMRule.new(4, 'b', 4, 'b', :right), # 跳过 b
    TMRule.new(4, 'c', 4, 'c', :right), # 跳过 c
    TMRule.new(4, '_', 5, 'c', :right) # 查找空格，写 c
  ])
=> #<struct DTMRulebook rules=[...]>
>> tape = Tape.new([], 'b', ['c', 'b', 'c', 'a'], '_')
=> #<Tape (b)cbca>
>> dtm = DTM.new(TMConfiguration.new(1, tape), [5], rulebook)
=> #<struct DTM ...>
>> dtm.run; dtm.current_configuration.tape
=> #<Tape bcbcab(_)>

除了它们每一个所表示的机器记住的字符串开头字符不同之外，这台机器的状态2、3 和4几乎完全相同，并且在这种情况下，在到达末端的时候它们都做了一些不同的事情。

这台机器只对由字符a、b、c 组成的字符串起作用。如果想要其对由字母表里任意字母组成的字符串起作用（或者字母数字字符，或者我们选择的更大集合），必须加入多得多的状态（为可能需要记住的每一个字符设置一个状态），还得加入多得多的与之匹配的规则。

如果用这种方式利用当前状态，我们可以设计出任凭纸带头来回移动仍能记住之前任何组合的图灵机，这实际上与给一台机器提供明确的“寄存器”作为内部存储有同样的能力，只不过代价是使用了大量的状态。

5.3.2　子例程

一台图灵机的规则手册是一个很长的、由极为低层次的指令组成的硬编码列表，因此在写这些规则时不忽略机器应该执行的高层次任务是很困难的。如果存在调用子例程的方法，设计一个规则手册会更容易一些：如果机器的某个部分能把所有这些规则存储成子例程，比如说叫“递增一个数”，那么我们的规则手册就不需要手工拼凑这些指令，而只需要说“现在递增一个数”，就能让一个数自增。或许这一次这种额外的灵活性能让我们设计出拥有新能力的机器。

但这实际上只是又一个关于便利性而不是能力的特性。就像有限自动机实现正则表达式片段一样（参见3.3.2 节），几个小图灵机可以连接在一起组成更大的图灵机，其中每一个小机器都实际上扮演着子例程的角色。我们之前看到的递增二进制数的机器，其状态和规则可构建入一个把两个二进制数相加的大一些的机器，而这个加法器本身还能构建成可执行乘法的更大的机器。

在小机器只需要由大机器的单个状态“调用”时，这很容易安排：只需要包含进小机器的副本，并把它的起始状态和接受状态与大机器的状态在子例程调用应该开始和结束的地方合并。这是我们使用递增机器组成一个加法器时期望的方式，因为规则手册的总体设计会根据需要重复单个任务——“如果第一个数不是0，就递减第一个数并递增第二个数”。在机器中递增只需要发生在一个地方，而且在递增的工作完成之后只会有一个地 方继续执行。

在我们想要在整个机器中的多个地方调用一个特定的子例程时，唯一的困难才会出现。一台图灵机没有办法存储“返回地址”，以让子例程知道一旦它结束之后应该返回到哪个状态，因此从表面上说，我们不能支持这种更通用的代码重用。但是就像在5.3.1 节做的那样，可以用复制解决此问题：我们不是只构建较小机器状态和规则的一份副本，而是会构建出许多份，较大机器中需要使用的每一个地方都对应一份。

例如，把“递增一个数”的机器转换成“给一个数加三”的机器，最简单的方式是把三份副本连接到一起完成“递增一个数，然后递增一个数，再递增一个数”的总体设计。这通过几个中间状态跟踪通向最终目标的过程，其中每一个都从“递增这个数”发起，然后返回一个不同的中间状态。

>> def increment_rules(start_state, return_state)
    incrementing = start_state
    finishing = Object.new
    finished = return_state

  [
    TMRule.new(incrementing, '0', finishing, '1', :right),
    TMRule.new(incrementing, '1', incrementing, '0', :left),
    TMRule.new(incrementing, '_', finishing, '1', :right),
    TMRule.new(finishing, '0', finishing, '0', :right),
    TMRule.new(finishing, '1', finishing, '1', :right),
    TMRule.new(finishing, '_', finished, '_', :left)
  ]
  end
=> nil
>> added_zero, added_one, added_two, added_three = 0, 1, 2, 3
=> [0, 1, 2, 3]
>> rulebook = DTMRulebook.new(
increment_rules(added_zero, added_one) +
increment_rules(added_one, added_two) +
increment_rules(added_two, added_three)
)
=> #<struct DTMRulebook rules=[...]>
>> rulebook.rules.length
=> 18
>> tape = Tape.new(['1', '0', '1'], '1', [], '_')
=> #<Tape 101(1)>
>> dtm = DTM.new(TMConfiguration.new(added_zero, tape), [added_three], rulebook)
=> #<struct DTM ...>
>> dtm.run; dtm.current_configuration.tape
=> #<Tape 111(0)_>

只要我们能接受机器规模的扩张，用这种方式组合状态和规则的能力可以构建任意大小和复杂度的图灵机，无需任何对子例程的明确支持。

5.3.3　多纸带

有时候机器可以通过扩展它的外部存储提高能力。例如，在一台下推自动机可以访问第二个栈的时候，它会变得更强大，因为两个栈可以用来模拟一个无限纸带：每一个栈存储一半要模拟的纸带，而这台PDA 可以在两个栈之间弹出和推入字符以模拟纸带头的动作，就像5.1.4 节中的Tape 实现那样。任何能访问无限纸带的有限状态机实际上都是一台图灵机，因此很明显增加一个额外的栈会让一台下推自动机更强大。

因此有理由期待通过增加一条或者多条纸带也能让图灵机更强大，这些纸带都有自己独立的纸带头。但事实又一次不是这样。一条图灵机的纸带通过交叉存取，会有足够的空间存储任意纸带数目的内容：包含abc、def 和ghi 的三条纸带可以一起存成adgbehcfi。如果我们在每一个交叉字符的边上放上一个空白方格，机器就有地方指示所有模拟的纸带头的位置了：通过使用字符X 指示每个纸带头的当前位置，我们可以用一条纸带a_dXg_b_e_hXcXf_i_表示纸带ab(c)、(d)ef 和g(h)i 的内容和纸带头的位置。

使用多条模拟的纸带对一台图灵机编程非常复杂，但累人的读、写以及纸带头的移动都可以封装成专门的状态和规则（“子例程”），这样机器的主要逻辑就不会变得过于复杂。在任何情况下，不管编程多么不方便，一台单纸带的图灵机最终都能执行多纸带机器能执行的任何任务，因此为一台图灵机增加额外的纸带并不会带来新的能力。

5.3.4　多维纸带

最后，尝试给一台图灵机更广阔的存储空间是很有诱惑力的。我们可以不使用线性纸带，而是提供无限的二维网格，并允许纸带头上下左右移动。每次需要移动纸带头快速访问外部存储的特定部分时，这都会很有用，而且不需要移动纸带头经过其他方格，这还允许我们在多个字符串周围留下无限的空白空间，这样它们中每一个都很容易变长，而不是每次在我们想要插入一个字符的时候只能手工整理整个纸带的信息以腾出空间来。

但不出意外的是，能用一维纸带模拟一个网格。最简单的方式就是使用两个一维纸带：主纸带实际存储数据，从纸带用来作为擦写空间。所模拟网格4 的每一行都存储在主纸带上，顶上的行优先，并用一个特殊的字符标识每一行的结尾。

4尽管网格本身是无限的，但只可能写入有限数目的字符，因此我们只需要存储包含所有空白字符的矩形区域即可。

主纸带的头像往常一样位于当前字符，因此为了在模拟网格上左右移动，机器只是简单地左右移动纸带头。如果纸带头指向了行尾的标识符，就会用一个子例程整理纸带以便让网格扩展出一个空间。

为了在模拟网格中上下移动，纸带头必须向左或者向右分别移动完整的一行。机器会先移动纸带头到当前行的开头或者结尾，并使用从纸带记录移动的距离，然后把纸带头在前一行或者下一行移动同样的偏移量。如果纸带头离开了所模拟网格的最顶部或者最底部，可以使用一个子例程分配一个纸带头能移动进去的新空行。

这个模拟确实要求一台机器有两条纸带，但对此我们也知道如何模拟。这样最终把模拟的网格存储在两条模拟的纸带上，而这两条纸带本身存储在一条原始的纸带上。这两层模拟引入了大量的额外规则和状态，而且执行所模拟机器的一步就要花很多步，但规模的增加和速度的减慢并不妨碍它（最终）完成本来应该做的事情。