Question

标签系统（tag system）是一个类似简化版图灵机的计算模型：标签系统不是在一条纸带上来回移动纸带头，而是反复在一个字符串的末尾增加新的字符并在开头处移除字符。在某方面，标签系统的字符串像是图灵机的纸带，但标签系统被限定在只能在字符串的两头操作，而且它只能朝着末尾“移动”。

标签系统的描述包括两部分：首先，一个规则集合，其中每一条规则定义当特定的字符出现在字符串的开头时，要给这个字符串添加的一些字符（例如“字符串的开头是字符 a 时，添加字符 bcd”）；其次，一个叫作删除数的数字，它定义了按照一个规则执行之后有多少字符要从字符串的开头删除。

下面是一个标签系统的例子：

· 字符串以a 开头时，添加字符 bc；

· 字符串以b 开头时，添加字符 caad；

· 字符串以c 开头时，添加字符ccd；

· 按照上面的任何规则执行之后，从字符串的开头删除三个字符，换句话说，删除数是 3。

我们可以通过反复遵照规则并删除字符直到字符串的首字符没有可用的规则，或者直到字符串的长度小于删除数 6，以此来执行一个标签系统的计算。我们用初始字符串 'aaaaaa'来运行一下示例标签系统：

6第二个条件可以防止我们删除比字符串所含有的字符数还多的字符。

当前字符串	可用规则
aaaaaa	字符串以a 开头时，添加字符 bc
aaabc	字符串以 a开头时，添加字符 bc
bcbc	字符串以 b 开头时，添加字符 caad
ccaad	字符串以 c 开头时，添加字符 ccd
adccd	字符串以 a 开头时，添加字符 bc
cdbc	字符串以 c 开头时，添加字符ccd
cccd	字符串以 c 开头时，添加字符 ccd
dccd	—

标签系统只能直接在字符串上操作，但我们也可以让它们对其他类型的值（例如数字）执行复杂的操作，只要用合适的方式把那些值编码成字符串就行。对数字编码的一种可能方式是：把数字n 表示成字符串 aa 后跟重复n 次的字符串 bb。例如，把数字 3 表示成字符串 aabbbbbb。

这个表示的某些方面可能看起来是多余的（可以只是把 3 表示成 aaa），但很快你就会发现，使用成对的字符，并在字符串的开头进行明确的标记很有用。

选定了数字的编码模式，就可以设计标签系统操作数字了。下面是一个对输入数翻倍的系统：

· 字符串以a 开头时，添加字符 aa；

· 字符串以b 开头时，添加字符 bbbb；

· 在执行完一个规则之后，从字符串的开头删掉两个字符（删除数为2）。

观察一下起始字符串是 aabbbb 时这个标签系统是如何表现的，这个字符串表示 2：

aabbbb → bbbbaa
     → bbaabbbb
     → aabbbbbbbb ( 表示数字 4)
     → bbbbbbbbaa
     → bbbbbbaabbbb
     → bbbbaabbbbbbbb
     → bbaabbbbbbbbbbbb
     → aabbbbbbbbbbbbbbbb ( 数字 8)
     → bbbbbbbbbbbbbbbbaa
     → bbbbbbbbbbbbbbaabbbb
...

很明显翻倍了，但这个标签系统却永远运行下去了（把由当前字符串表示的数翻倍，然后再翻倍，然后再翻倍），这真不是我们想要的。为了设计一个只对一个数字翻倍一次然后停机的系统，我们需要使用不同的字符对结果进行编码，以保证不再触发新一轮的翻倍。我们可以通过放松编码模式，允许字符 c 和 d 替换 a 和 b，然后修改规则，在表示翻倍之后的数时使用 cc 和 dddd 而不是 aa 和 bbbb。

这样改变之后，计算看起来像是这样：

aabbbb → bbbbcc
     → bbccdddd
     → ccdddddddd（数字 4，用 c 和 d 而不是 a 和 b 进行编码）

修改后的系统在到达 ccdddddddd 时会停止，因为没有针对 c 开头字符串的规则。

在这种情况下，我们只是依赖字符 c 适时停止计算，因此完全可以在结果中重用 b 而不是用 d 来替换它，但使用超出必要的字符没有什么害处。

使用不同的字符集合来对输入和输出值进行编码会更清晰一些。就像我们很快将要看到的那样，这还能更容易地把几个小的标签系统组合成一个大的系统，可以通过把一个系统的输出编码与另一个系统的输入编码匹配做到。

为了在 Ruby 中模拟标签系统，我们需要一个单规则的实现（TagRule），一个规则集合的实现（TagRulebook），以及标签系统自身的实现（TagSystem）：

class TagRule < Struct.new(:first_character, :append_characters)
  def applies_to?(string)
    string.chars.first == first_character
  end

  def follow(string)
    string + append_characters
  end
end

class TagRulebook < Struct.new(:deletion_number, :rules)
  def next_string(string)
    rule_for(string).follow(string).slice(deletion_number..-1)
  end

  def rule_for(string)
    rules.detect { |r| r.applies_to?(string) }
  end
end

class TagSystem < Struct.new(:current_string, :rulebook)
  def step
    self.current_string = rulebook.next_string(current_string)
  end
end

这个实现允许我们单步执行标签系统的计算，一次只执行一个规则。让我们试试之前的对数字翻倍的例子，这次对数字 3（aabbbbbb）翻倍：

>> rulebook = TagRulebook.new(2, [TagRule.new('a', 'aa'), TagRule.new('b', 'bbbb')])
=> #<struct TagRulebook ...>
>> system = TagSystem.new('aabbbbbb', rulebook)
=> #<struct TagSystem ...>
>> 4.times do
    puts system.current_string
    system.step
  end; puts system.current_string
aabbbbbb
bbbbbbaa
bbbbaabbbb
bbaabbbbbbbb
aabbbbbbbbbbbb
=> nil

因为这个标签系统会永远运行，所以我们只能在结果出现之前预先知道执行多少步（这种情况下是 4 步），但如果我们使用把结果用c 和 d编码的修改版本，就可以让它自动停下来。增加代码来支持它：

class TagRulebook
  def applies_to?(string)
    !rule_for(string).nil? && string.length >= deletion_number
  end
end

class TagSystem
  def run
    while rulebook.applies_to?(current_string)
      puts current_string
      step
    end

    puts current_string
  end
end

现在可以只对标签系统的停机版本调用 TagSystem#run，并让其在合适时机自然停止：

>> rulebook = TagRulebook.new(2, [TagRule.new('a', 'cc'), TagRule.new('b', 'dddd')])
=> #<struct TagRulebook ...>
>> system = TagSystem.new('aabbbbbb', rulebook)
=> #<struct TagSystem ...>
>> system.run
aabbbbbb
bbbbbbcc
bbbbccdddd
bbccdddddddd
ccdddddddddddd
=> nil

这个实现允许我们探索标签系统能做的其他事情。使用我们的编码模式，很容易设计系统执行其他的数字操作，就像下面这个对一个数字减半的系统：

>> rulebook = TagRulebook.new(2, [TagRule.new('a', 'cc'), TagRule.new('b', 'd')])
=> #<struct TagRulebook ...>
>> system = TagSystem.new('aabbbbbbbbbbbb', rulebook)
=> #<struct TagSystem ...>
>> system.run
aabbbbbbbbbbbb
bbbbbbbbbbbbcc
bbbbbbbbbbccd
bbbbbbbbccdd
bbbbbbccddd
bbbbccdddd
bbccddddd
ccdddddd
=> nil

还有这个递增一个数字的系统：

>> rulebook = TagRulebook.new(2, [TagRule.new('a', 'ccdd'), TagRule.new('b', 'dd')])
=> #<struct TagRulebook ...>
>> system = TagSystem.new('aabbbb', rulebook)
=> #<struct TagSystem ...>
>> system.run
aabbbb
bbbbccdd
bbccdddd
ccdddddd
=> nil

我们可以把两个标签系统联结一起，只要第一个系统的输出编码与第二个系统的输入编码匹配即可。下面是一个简单的系统，它使用字符c和 d 对递增规则的输入进行编码，并用e 和 f 对它们的输出进行编码，以此把翻倍和递增规则组合到一起：

>> rulebook = TagRulebook.new(2, [
    TagRule.new('a', 'cc'), TagRule.new('b', 'dddd'), # double
    TagRule.new('c', 'eeff'), TagRule.new('d', 'ff') # increment
  ])
=> #<struct TagRulebook ...>
>> system = TagSystem.new('aabbbb', rulebook)
=> #<struct TagSystem ...>
>> system.run
aabbbb ( 数字 2)
bbbbcc
bbccdddd
ccdddddddd ( 数字 4) ➊
ddddddddeeff
ddddddeeffff
ddddeeffffff
ddeeffffffff
eeffffffffff ( 数字 5) ➋
=> nil

➊ 翻倍规则把 2 转成 4，用字符 c 和 d 编码。 ➋ 递增规则把 4 转成 5，这次使用 e 和 f 编码。

除了把数字转成其他数字之外，标签系统还可以检查它们的数学特性。下面是测试一个数是奇数还是偶数的标签系统：

>> rulebook = TagRulebook.new(2, [
    TagRule.new('a', 'cc'), TagRule.new('b', 'd'),
    TagRule.new('c', 'eo'), TagRule.new('d', ''),
    TagRule.new('e', 'e')
  ])
=> #<struct TagRulebook ...>

如果输入代表一个偶数，这个系统会停止在单字符 e（代表“偶数”）：

>> system = TagSystem.new('aabbbbbbbb', rulebook)
=> #<struct TagSystem ...>
>> system.run
aabbbbbbbb (the number 4)
bbbbbbbbcc
bbbbbbccd
bbbbccdd
bbccddd
ccdddd ➊
ddddeo ➋
ddeo
eo ➌
e ➍
=> nil

➊ a 和 b 把输入减半；ccdddd 代表数字 2。 ➋ c 规则删掉前导的cc 对，并添加字符 eo，它们中间的一个会形成最后的结果。 ➌ 空的 d 规则会耗尽所有的前导 dd 对，只留下 eo。 ➍ e 规则只会用e 替换eo，然后系统停机。

如果输入的数为奇数，那么结果就是字符串 o（代表“奇数”）：

>> system = TagSystem.new('aabbbbbbbbbb', rulebook)
=> #<struct TagSystem ...>
>> system.run
aabbbbbbbbbb ( 数字 5)
bbbbbbbbbbcc
bbbbbbbbccd
bbbbbbccdd
bbbbccddd
bbccdddd
ccddddd ➊
dddddeo
dddeo
deo ➋
o ➌
=> nil

➊ 数字像以前一样减半，但因为这次是奇数，所以结果是一个奇数个 d 组成的字符串。我们对数字的编码模式只使用成对的字符，因此 ccddddd 不代表任何数，但因为它含有“两个半”成对的字符 d，可以不正式地把它看成是数字 2.5。

➋ 所有前导的 dd 对都被删掉了，在最终的 eo 之前留下了一个 d。 ➌ 残留的 d 被删掉了，并带走了 e，只留下 o，然后系统停机。

为了让这个标签系统工作，拥有大于 1 的删除数至关重要。因为每个第二字符都会触发一个规则，我们可以通过在特定的触发位置安排特定的字符出现（或者不出现）来影响系统的行为。这种让字符在删除行为中同步或者不同步出现的技术是设计强大标签系统的关键。

这些数字操作技术可以用来模拟一台图灵机。在像标签系统这么简单的东西之上构建模拟的图灵机涉及大量细节，但其中一种工作方式像是下面这样。

1.作为可能最简单的例子，让一台图灵机的纸带只使用两个字符，我们将称它们为 0 和1，其中 0 扮演空白字符的角色。

2.把图灵机的纸带分成两部分：左半部分含有纸带头下的字符和所有它左边的字符，右半部分含有纸带头右边的所有字符。

3.把纸带的左半部分作为一个二进制数：如果最初的纸带类似 0001101(0)0011000，那么左半部分就是二进制数 11010，这是十进制数 26。

4.把纸带的右半部分作为一个反写的二进制数：示例纸带的右半部分是二进制数 1100，即十进制数 12。

5.把这两个数编码成一个适合由标签系统使用的字符串。对于示例纸带，我们可以使用aa 后跟 26 份 bb，然后 cc 后跟 12 份 dd。

6.使用简单的翻倍、减半、递增、递减，以及奇偶检查模拟从纸带上读、向纸带写以及移动纸带头。例如，我们通过对左半部分数字翻倍， 对右半部分数字减半7 来在示例纸带上向右移动纸带头：翻倍 26 得到 52，二进制就是 110100；12 的一半是 6，二进制 是 110。因此新的纸带看起来是 011010(0)011000。从纸带上读取意味着检查表示纸带左半部分的数字是奇数还是偶数，而向纸带上写一个 1 或者 0 意思是对那个数递增或者递减。

7对一个数翻倍在二进制表示上就是所有的数字左移一位，而减半就是把所有的数字右移一位。

7.使用选择的字符来对左右纸带数进行编码，以此来表示所模拟图灵机的当前状态：或许机器处于状态 1，我们使用 a、b、c 和 d 来对纸带进行编码，但它转移到状态 2 时，使用e、f、g 和 h 来编码，以此类推。

8.把每一个图灵机规则转成一个标签系统，它会用合适的方式对当前字符串进行重写。读取一个 0，写入一个 1，向右移动纸带头并进入状态 2 的规则变成的标签系统，会检查左侧纸带的数是偶数，对其递增，翻倍左边纸带的数，同时减半右边纸带的数，然后产生一个使用状态 2 的字符编码的字符串。

9.把这些独立的标签系统组合起来，就是一个可以模拟图灵机每一条规则的大系统。

对于标签系统如何模拟图灵机工作的完整说明，请看 Matthew Cook 在 http://www.complex-systems.com/pdf/15-1-1.pdf 中 2.1 节所做的简洁解释。

Cook 的模拟比这里描述的更复杂。它使用当前字符串的“对齐”来表示所模拟纸带头下面的字符，而不是把它作为纸带的一部分，而且它很容易扩展，通过增加标签系统的删除数来以任意数目的字符模拟一台图灵机。

标签系统可以模拟任意图灵机的事实，意味着它也是通用的。