Question

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

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

5.1.1　存储

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

——阿兰·图灵，《论可计算数及其在判定性问题上的应用》， http://dx.doi.org/10.1112/plms/s2-42.1.23o

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

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

我们已经知道，下推自动机只能访问其外部存储的一个固定位置（栈的顶部），但这似乎对图灵机来说限制性太强了。提供一条纸带的目的就是允许在纸带上的任何位置存储任意量的数据，并以任意顺序读取，那么我们如何设计一台能与整条纸带交互的机器呢？

一种选择是让纸带可以被随机寻址访问，就像计算机的RAM 一样给每个方格标记一个独立的数字地址，这样机器可以立即读取和写入任何位置。这增加了不必要的复杂性，而且需要规划出细节上的东西，比如如何给一条无限纸带的所有方格分配地址，以及在它需要访问方格时如何指定方格的地址。

传统的图灵机不是这样，而是使用更简单的安排：用一个纸带头（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' 时对机器执行的跟踪。纸带头当前指向的字符会由括号包围，而下划线表示输入字符串某一端的空白方格。

状态	是否接受	纸带内容	动作
1	否	_101(1)__	写入0，左移
1	否	__10(1)0_	写入0，左移
1	否	__1(0)00	写入1，右移，转移到2
2	否	__11(0)0_	右移
2	否	_110(0)__	右移
2	否	1100(_)__	左移，转移到状态3
3	是	_110(0)__	—

严格来说，把纸带头移回它的初始位置并不必要（如果我们把状态2 作为接受状态，则一旦机器成功地把0 替换成1，它会立即停止，而纸带仍会包含正确的结果），但这是一个值得要的特性，因为它把纸带头放到位之后，机器只要简单地把状态改变回状态1 就可以再次运行。通过多次运行机器，我们可以不断递增存储在纸带上的数。这个功能可以重用，作为更大机器的一部分，比如说把两个二进制数相加或相乘。

5.1.2　规则

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

——阿兰· 图灵，《论可计算数及其在判定性问题上的应用》

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

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

· 机器的当前状态；

· 必须出现在纸带头当前位置的字符；

· 机器的下一状态；

· 要写入纸带头当前位置的字符；

· 写入纸带之后纸带头的移动方向（向左还是向右）。

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

我们还假设了纸带头每步都要移动。这就不太可能书写一个不移动纸带头就更新状态或者纸带内容的规则，但我们可以通过一个规则做出需要的改变以得到同样的效果，然后再通过一个规则把纸带头移回原始位置。

递增一个二进制数的图灵机写成这种类型的话将有6 个规则：

· 处于状态 1 并且读入一个 0 时，写入一个 1，右移，然后进入状态 2；

· 处于状态 1 并且读入一个 1 时，写入一个 0，左移，然后保持在状态 1；

· 处于状态 1 并且读到一个空白时，写入一个 1，右移，然后进入状态 2；

· 处于状态 2 并且读到一个 0 时，写入一个 0，右移，然后保持在状态 2；

· 处于状态 2 并且读入一个 1 时，写入一个 1，右移，然后保持在状态 2；

· 处于状态 2 并且读到一个空白时，写入一个空白，左移，然后进入状态 3。

与在有限自动机和下推自动机中使用的图类似，我们也可以展示机器的状态和规则：

事实上，除去箭头上的标签，这很像一个DFA 示意图。标签a/b;L 表示一条规则，它从纸带上读取字符a，写入字符b，然后把纸带头向左移动一个方格； 标签a/b;R 表示的规则几乎一样，只是会把纸带头向右而不是向左移动。

我们看一下如何使用图灵机解决下推自动机无法处理的字符串识别问题：要识别的字符串包含一个或者多个字符a，后面跟随着同样数目的b 和c（如'aaabbbccc'）。解决这个问题的图灵机有 6 个状态和 16 个规则：它大致像这样工作：

1.通过不断把纸带头向右移扫描输入字符串，直到发现一个a 为止，然后通过用X替换a来把它删除（状态1）；

2.向右扫描寻找一个b，然后删除（状态2）；

3.向右扫描寻找一个c，然后删除（状态3）；

4.向右扫描寻找输入字符串的结尾（状态4），然后向左扫描寻找输入字符串的开头（状态5）；

5.重复这些步骤，直到所有的字符都已被删除为止。

如果输入字符串是由一个或多个字符a 以及同样数目的b 和c 组成的，那么机器将会重复跨越整个字符串几次，每次跨越都会删除一个字符，然后在整个字符串都被删掉的时候进入到一个接受状态。下面是在输入为'aabbcc' 时的执行跟踪。

状态	是否接受	纸带内容	动作
1	否	______(a)abbcc_	写入X，右移，转移到状态2
2	否	_____X(a)bbcc__	右移
2	否	____Xa(b)bcc___	写入X，右移，转移到状态3
3	否	___XaX(b)cc____	右移
3	否	__XaXb(c)c_____	写入X，右移，转移到状态4
4	否	_XaXbX(c)______	右移
4	否	XaXbXc(_)______	左移，转移到状态5
5	否	_XaXbX(c)______	左移
5	否	__XaXb(X)c_____	左移
5	否	___XaX(b)Xc____	左移
5	否	____Xa(X)bXc___	左移
5	否	_____X(a)XbXc__	左移
5	否	______(X)aXbXc_	左移
5	否	______(_)XaXbXc	右移，转移到状态1
1	否	______(X)aXbXc_	右移
1	否	_____X(a)XbXc__	写入X，右移，转移到状态2
2	否	____XX(X)bXc___	右移
2	否	___XXX(b)Xc____	写入X，右移，转移到状态3
3	否	__XXXX(X)c_____	右移
3	否	_XXXXX(c)______	写入X，右移，转移到状态4
4	否	XXXXXX(_)______	左移，转移到状态5
5	否	_XXXXX(X)______	左移
5	否	__XXXX(X)X_____	左移
5	否	___XXX(X)XX____	左移
5	否	____XX(X)XXX___	左移
5	否	_____X(X)XXXX__	左移
5	否	______(X)XXXXX_	左移
5	否	______(_)XXXXXX	右移，转移到状态1
1	否	______(X)XXXXX_	右移
1	否	_____X(X)XXXX__	右移
1	否	____XX(X)XXX___	右移
1	否	___XXX(X)XX____	右移
1	否	__XXXX(X)X_____	右移
1	否	_XXXXX(X)______	右移
1	否	XXXXXX(_)______	左移，转移到状态6
6 是	_XXXXX(X)______	—

这台机器能够工作是因为扫描阶段规则的准确选择。例如，机器处于状态3（向右扫描并查找c）的时候，它能执行的规则只能是移动纸带头经过b 和X。如果机器遇到了其他字符（如非期望的a），它是没有规则可以遵守的，在这种情况下它会进入隐含的卡死状态停止执行，并会因此拒绝这个输入。

我们通过假设输入只包含字符a、b 和c 来保持简单，但如果不是这样，机器也不会正常工作。例如，它会接受字符串'XaXXbXXXc'，即使这个字符串本来应该被拒绝。为了正确地处理这种输入，我们需要增加更多的规则和状态扫描整个字符串，以检查在机器开始删除字符之前这个字符串不包含任何非期望的字符。

5.1.3　确定性

对于设计成确定性的一台特定的图灵机，它只能遵守和确定性下推自动机一样的约束（参见4.1.3 节），但这次我们不用担心自由移动，因为图灵机没有自由移动。

要根据图灵机的当前状态和当前纸带头下的字符来选择它的下一个动作，因此一台确定性机器只能有由状态和字符组合成的一个规则——“无矛盾”规则，这是为了避免下一个动作有任何的歧义。简单起见，我们会像处理DPDA 时那样，放松“无遗漏”规则，并假设在没有规则可用的时候机器可以进入一个隐含的卡死状态，而不是坚持对于每一个可能的 情况都要有一个规则。

5.1.4　模拟

我们已经对一台确定性图灵机应该如何工作有了很好的认识，现在来构建一个Ruby 的模拟以便可以看到它的执行。

第一步是实现图灵机的纸带。很显然这个实现不得不存储写到纸带上的字符，但它还需要记住纸带头的当前位置，以便模拟出来的机器可以读取当前字符，在当前位置写入一个新的字符，并左右移动纸带头到达其他位置。

做到这一点的一个优雅方式是把纸带分成三部分（纸带头左边的全部字符、纸带头下的一个字符、右边的所有字符），每一部分分别存储。这让读写当前字符变得非常容易，而移动纸带头可以通过在所有三个部分之间慢慢移动字符实现。例如，向右移动一个方格，意味着之前的当前字符成为了纸带头左边的最后一个字符，而之前纸带头右边的第一个字符成为了当前字符。

我们的实现还必须维护纸带无限长而且填满空白方格的假象，但幸好并不需要一个无限大的数据结构。在任意给定时刻唯一能被读取的是纸带头下的位置，因此在纸带头移动超出了已经写在纸带上的有限数目的非空字符时。我们只需安排一个空白字符出现。为此，我们需要预先知道哪个字符代表一个空白方格，然后只要进入到纸带上未经探索的区域，就可以让这个字符自动出现在纸带头下。

因此，一条纸带的基本表示看起来像这样：

class Tape < Struct.new(:left, :middle, :right, :blank)
  def inspect
    "#<Tape #{left.join}(#{middle})#{right.join}>"
  end
end

因此可以创建一条纸带并读取纸带头下面的字符：

>> tape = Tape.new(['1', '0', '1'], '1', [], '_')
=> #<Tape 101(1)>
>> tape.middle
=> "1"

我们可以增加操作，向当前纸带位置1 写入并把纸带头左右移动：

1就像栈一样，纸带是纯功能性的：写入纸带和移动纸带头都是非破坏性操作，只会返回一个新的Tape，而不是更新已有的对象。

class Tape
  def write(character)
    Tape.new(left, character, right, blank)
  end

  def move_head_left
    Tape.new(left[0..-2], left.last || blank, [middle] + right, blank)
  end

  def move_head_right
    Tape.new(left + [middle], right.first || blank, right.drop(1), blank)
  end
end

现在可以向纸带写入，并来回移动纸带头：

>> tape
=> #<Tape 101(1)>
>> tape.move_head_left
=> #<Tape 10(1)1>
>> tape.write('0')
=> #<Tape 101(0)>
>> tape.move_head_right
=> #<Tape 1011(_)>
>> tape.move_head_right.write('0')
=> #<Tape 1011(0)>

在第4 章，我们使用配置一词来代表下推自动机状态和栈的组合，同样的理念在这里也会很有帮助。可以说一个图灵机的配置是一个状态和一条纸带的组合，并且可以直接处理这些配置的图灵机规则：

class TMConfiguration < Struct.new(:state, :tape)
end

class TMRule < Struct.new(:state, :character, :next_state,
              :write_character, :direction)
  def applies_to?(configuration)
    state == configuration.state && character == configuration.tape.middle
  end
end

只有在机器的当前状态和纸带头下的当前字符与其表达式匹配时，规则才能应用：

>> rule = TMRule.new(1, '0', 2, '1', :right)
=> #<struct TMRule
    state=1,
    character="0",
    next_state=2,
    write_character="1",
    direction=:right
  >
>> rule.applies_to?(TMConfiguration.new(1, Tape.new([], '0', [], '_')))
=> true
>> rule.applies_to?(TMConfiguration.new(1, Tape.new([], '1', [], '_')))
=> false
>> rule.applies_to?(TMConfiguration.new(2, Tape.new([], '0', [], '_')))
=> false

知道一个规则能在一个特定的配置下应用之后，我们需要能够通过写入一个新字符、移动纸带头以及按照规则改变机器状态来更新该配置：

class TMRule
  def follow(configuration)
    TMConfiguration.new(next_state, next_tape(configuration))
  end

  def next_tape(configuration)
    written_tape = configuration.tape.write(write_character)

    case direction
    when :left
      written_tape.move_head_left
    when :right
      written_tape.move_head_right
    end
  end
end

这些代码看起来工作得很好：

>> rule.follow(TMConfiguration.new(1, Tape.new([], '0', [], '_')))
=> #<struct TMConfiguration state=2, tape=#<Tape 1(_)>>

DTMRulebook 的实现几乎与DFARulebook 和DPDARulebook 一样，只是方法#next_configuration没有用字符作为参数，这是因为没有外部的输入可供读取字符（只有纸带，而纸带已经是配置的一部分了）：

class DTMRulebook < Struct.new(:rules)
  def next_configuration(configuration)
    rule_for(configuration).follow(configuration)
  end

  def rule_for(configuration)
    rules.detect { |rule| rule.applies_to?(configuration) }
  end
end

我们现在可以为“递增二进制数”的图灵机创建一个DTMRulebook，并手工单步执行一些配置：

>> rulebook = DTMRulebook.new([
    TMRule.new(1, '0', 2, '1', :right),
    TMRule.new(1, '1', 1, '0', :left),
    TMRule.new(1, '_', 2, '1', :right),
    TMRule.new(2, '0', 2, '0', :right),
    TMRule.new(2, '1', 2, '1', :right),
    TMRule.new(2, '_', 3, '_', :left)
  ])
=> #<struct DTMRulebook rules=[...]>
>> configuration = TMConfiguration.new(1, tape)
=> #<struct TMConfiguration state=1, tape=#<Tape 101(1)>>
>> configuration = rulebook.next_configuration(configuration)
=> #<struct TMConfiguration state=1, tape=#<Tape 10(1)0>>
>> configuration = rulebook.next_configuration(configuration)
=> #<struct TMConfiguration state=1, tape=#<Tape 1(0)00>>
>> configuration = rulebook.next_configuration(configuration)
=> #<struct TMConfiguration state=2, tape=#<Tape 11(0)0>>

把所有这些封装成一个DTM 类很方便，这样就像第2 章里实现小步语义时那样，我们可以有#step 和#run 方法：

class DTM < Struct.new(:current_configuration, :accept_states, :rulebook)
  def accepting?
    accept_states.include?(current_configuration.state)
  end

  def step
    self.current_configuration = rulebook.next_configuration(current_configuration)
  end

  def run
    step until accepting?
  end
end

我们现在有了一台确定型图灵机的模拟，因此给它一些输入试验一下：

>> dtm = DTM.new(TMConfiguration.new(1, tape), [3], rulebook)
=> #<struct DTM ...>
>> dtm.current_configuration
=> #<struct TMConfiguration state=1, tape=#<Tape 101(1)>>
>> dtm.accepting?
=> false
>> dtm.step; dtm.current_configuration
=> #<struct TMConfiguration state=1, tape=#<Tape 10(1)0>>
>> dtm.accepting?
=> false
>> dtm.run
=> nil
>> dtm.current_configuration
=> #<struct TMConfiguration state=3, tape=#<Tape 110(0)_>>
>> dtm.accepting?
=> true

就像对待DPDA 模拟一样，为了能优雅地处理卡死状态的图灵机我们需要再多做一些工作：

>> tape = Tape.new(['1', '2', '1'], '1', [], '_')
=> #<Tape 121(1)>
>> dtm = DTM.new(TMConfiguration.new(1, tape), [3], rulebook)
=> #<struct DTM ...>
>> dtm.run
NoMethodError: undefined method 'follow' for nil:NilClass

这次我们不需要一个卡死状态的特殊表示了。与PDA 不同，图灵机没有外部输入，因此可以通过看它的规则手册和当前配置判断其是否处于卡死状态：

class DTMRulebook
  def applies_to?(configuration)
    !rule_for(configuration).nil?
  end
end

class DTM
  def stuck?
    !accepting? && !rulebook.applies_to?(current_configuration)
  end

  def run
    step until accepting? || stuck?
  end
end

现在模拟会注意到它卡住了并且自动停止：

>> dtm = DTM.new(TMConfiguration.new(1, tape), [3], rulebook)
=> #<struct DTM ...>
>> dtm.run
=> nil
>> dtm.current_configuration
=> #<struct TMConfiguration state=1, tape=#<Tape 1(2)00>>
>> dtm.accepting?
=> false
>> dtm.stuck?
=> true

只是为了好玩，下面是我们之前看到的用来识别'aaabbbccc' 这样的字符串的图灵机：

>> rulebook = DTMRulebook.new([
    # 状态1：向右扫描，查找a
    TMRule.new(1, 'X', 1, 'X', :right), # 跳过 X
    TMRule.new(1, 'a', 2, 'X', :right), # 删除 a，进入状态 2
    TMRule.new(1, '_', 6, '_', :left), # 查找空格，进入状态 6 （接受）

    # 状态2：向右扫描，查找b
    TMRule.new(2, 'a', 2, 'a', :right), # 跳过 a
    TMRule.new(2, 'X', 2, 'X', :right), # 跳过 X
    TMRule.new(2, 'b', 3, 'X', :right), # 删除 b，进入状态 3

    # 状态3：向右扫描，查找c
    TMRule.new(3, 'b', 3, 'b', :right), # 跳过 b
    TMRule.new(3, 'X', 3, 'X', :right), # 跳过 X
    TMRule.new(3, 'c', 4, 'X', :right), # 删除 c，进入状态 4

    # 状态4：向右扫描，查找字符串结束标记
    TMRule.new(4, 'c', 4, 'c', :right), # 跳过 c
    TMRule.new(4, '_', 5, '_', :left), # 查找空格，进入状态 5

    # 状态5：向左扫描，查找字符串开始标记
    TMRule.new(5, 'a', 5, 'a', :left), # 跳过 a
    TMRule.new(5, 'b', 5, 'b', :left), # 跳过 b
    TMRule.new(5, 'c', 5, 'c', :left), # 跳过 c
    TMRule.new(5, 'X', 5, 'X', :left), # 跳过 X
    TMRule.new(5, '_', 1, '_', :right) # 查找空格，进入状态 1
  ])
=> #<struct DTMRulebook rules=[...]>
>> tape = Tape.new([], 'a', ['a', 'a', 'b', 'b', 'b', 'c', 'c', 'c'], '_')
=> #<Tape (a)aabbbccc>
>> dtm = DTM.new(TMConfiguration.new(1, tape), [6], rulebook)
=> #<struct DTM ...>
>> 10.times { dtm.step }; dtm.current_configuration
=> #<struct TMConfiguration state=5, tape=#<Tape XaaXbbXc(c)_>>
>> 25.times { dtm.step }; dtm.current_configuration
=> #<struct TMConfiguration state=5, tape=#<Tape _XXa(X)XbXXc_>>
>> dtm.run; dtm.current_configuration
=> #<struct TMConfiguration state=6, tape=#<Tape _XXXXXXXX(X)_>>

这个实现很容易构建，只要我们有了表示纸带和规则手册的数据结构，模拟一台图灵机并不难。当然，阿兰·图灵特意让它们保持简单以便容易构建和推导，并且我们将在之后（5.4 节）看到实现的简单性也是一个重要属性。