Question

循环标签系统（cyclic tag system）是施加了一些额外限制的更简单的标签系统。

· 循环标签系统的字符串只能包含两个字符：0 和 1。

· 循环标签系统的规则只会在当前字符串以1 开始而不是 0 开始的时候才会应用。8

· 循环标签系统的删除数总是 1。

8循环标签系统的规则没有必要说“字符串以 1 开始时，添加字符 011”，因为第一部分已经假定了——只需要“添加字符 011”就足够了。

这些约束本身对于支持任何有用的计算来说都过于苛刻了，因此作为补偿循环标签系统有一个额外的特性：循环标签系统的规则手册中的第一条规则是执行开始时的当前规则，并且在计算的每一步之后，规则手册中的下一个规则就成为了当前规则，在到达规则手册结尾的时候又会回到第一个规则。

这种系统被称为“循环的”，是因为当前规则不断地在规则手册中循环。一个当前规则，再结合上每条规则都只会应用到 1 开头的字符串这一约束，避免了在每一步执行中不得不遍历规则手册查找可用规则的开销。如果首字符是 1，那么就应用当前规则，否则，就没有可用的规则。

作为一个例子，我们看一下拥有三个规则的循环标签系统，三个规则分别添加字符1，0010 和 10。下面是以字符串 11 开始时的情形：

当前字符串	当前规则	可以应用规则吗
11	添加字符 1	是
11	添加字符 0010	是
10010	添加字符 10	是
001010	添加字符 1	否
01010	添加字符 0010	否
1010	添加字符 10	是
01010	添加字符 1	否
1010	添加字符0010	是
0100010	添加字符 10	否
100010	添加字符 1	是
000101	添加字符 0010	否
00101	添加字符 10	否
0101	添加字符 1	否
101	添加字符0010	是
010010	添加字符 10	否
10010	添加字符 1	是
00101	添加字符0010	否
⋮	⋮	⋮

尽管这个系统极其简单，我们也能看到一点点复杂的行为：接下来要发生什么并不明显。稍微思考一下，可以证明这个系统将会永远运行下去而不是缩减成一个空字符串，这是因为每个规则都添加一个 1，因此只要最初的字符串含有一个 1，它就不会完全结束。9 但是当前字符串会断断续续地持续变长，还是会进入扩张和收缩的反复模式呢？只看规则没法回答这个问题，需要一直运行这个系统以查明会发生什么。

9循环标签系统与正常的标签系统不同，它在没有规则可用的时候仍然会一直运行，不然的话它就什么也做不了。让循环标签系统停止运行的唯一方式就是使它的当前字符串成为空。例如在初始字符串完全由字符 0 组成的时候，总会出现空字符串。

我们已经有了常见标签系统的一个 Ruby 实现，因此模拟循环标签系统不需要太多的额外工作。我们通过简单的子类化TagRule 实现CyclicTagRule 并把 '1' 硬编码为它的 first_character：

class CyclicTagRule < TagRule
  FIRST_CHARACTER = '1'

  def initialize(append_characters)
    super(FIRST_CHARACTER, append_characters)
  end

  def inspect
    "#<CyclicTagRule #{append_characters.inspect}>"
  end
end

#initialize 是 一个 构 造方法， 在一个类的实例被创建时会自动调用。CyclicTagRule#initialize 从超类 TagRule 调用构造函数，以此来设置first_character 和 append_character 属性。

循环标签系统的规则工作方式有些许的不同，因此我们将从头构建一个 CylicTagRulebook类，提供对 #applies_to? 和#next_string 的新实现：

class CyclicTagRulebook < Struct.new(:rules)
  DELETION_NUMBER = 1

  def initialize(rules)
    super(rules.cycle)
  end

  def applies_to?(string)
    string.length >= DELETION_NUMBER
  end

  def next_string(string)
    follow_next_rule(string).slice(DELETION_NUMBER..-1)
  end

  def follow_next_rule(string)
    rule = rules.next

      if rule.applies_to?(string)
        rule.follow(string)
      else
        string
      end
    end
  end

不像TagRulebook，即使当前规则不能应用，CyclicTagRulebook 也总是应用到非空字符串上。

Array#cycle 创建一个 Enumerator（参见 6.1.11 节“原始 Ruby 流”部分），它会永远地循环访问一个数组的元素：

>> numbers = [1, 2, 3].cycle
=> #<Enumerator: [1, 2, 3]:cycle>
>> numbers.next
=> 1
>> numbers.next
=> 2
>> numbers.next
=> 3
>> numbers.next
=> 1
>> [:a, :b, :c, :d].cycle.take(10)
=> [:a, :b, :c, :d, :a, :b, :c, :d, :a, :b]

这恰好是我们对循环标签系统当前规则所要求的行为，因此CyclicTagRulebook#initialize 把这些循环中的一个赋给规则属性，然后每次对 #follow_next_rule 的调用都使用rules.next 得到循环中的下一条规则。

现在我们可以创建由 CyclicTagRules 组 成 的 CyclicTagRulebook， 然后把它放到一个TagSystem 里观察其工作情况：

>> rulebook = CyclicTagRulebook.new([
    CyclicTagRule.new('1'), CyclicTagRule.new('0010'), CyclicTagRule.new('10')
  ])
=> #<struct CyclicTagRulebook ...>
>> system = TagSystem.new('11', rulebook)
=> #<struct TagSystem ...>
>> 16.times do
    puts system.current_string
    system.step
  end; puts system.current_string
11
11
10010
001010
01010
1010
01010
1010
0100010
100010
000101
00101
0101
101
010010
10010
00101
=> nil

这与我们手工单步执行时候看到的行为相同。继续吧：

>> 20.times do
    puts system.current_string
    system.step
  end; puts system.current_string
00101
0101
101
011
11
110
101
010010
10010
00101
0101
101
011
11
110
101
010010
10010
00101
0101
101
=> nil

以字符串 11 开始时，这个系统确实进入到重复的行为中：在一段不稳定阶段过后，会出现 9 个连续的字符串（101、010010、10010、00101……）并会一直这么重复下去。当然，如果我们改变了初始字符串或者任意规则，那长期的行为都会变得不同。

循环标签系统极其受限（它们的规则不灵活，只有两个字符，删除数也是最低值），但令人吃惊的是，仍然可以使用它们模拟任何标签系统。

由一个循环标签系统对一个正常标签系统的模拟大概像下面描述的这样工作。

1.决定标签系统的字母表：它使用的字符集合。

2.设计编码模式，把每一个字符与一个适合用在循环标签系统里的唯一字符串关联起来（也就是只包含 0 和 1）。

3.把每一个原始系统的规则转换成一个循环标签系统的规则，方法是对它添加的字符进行编码。

4.用空规则填补循环标签系统的规则手册，模拟原始标签系统的删除数。

5.对原始标签系统的输入字符串进行编码，并使用它作为循环标签系统的输入。

下面就来具体实现上述思路。首先，需要能得到一个标签系统所使用的字符：

class TagRule
  def alphabet
    ([first_character] + append_characters.chars.entries).uniq
  end
end

class TagRulebook
  def alphabet
    rules.flat_map(&:alphabet).uniq
  end
end

class TagSystem
  def alphabet
    (rulebook.alphabet + current_string.chars.entries).uniq.sort
  end
end

我们可以在 7.5 节数字递增的标签系统上测试这个功能。TagSystem#alphabet 表明这个系统使用字符 a、b、c 和 d：

>> rulebook = TagRulebook.new(2, [TagRule.new('a', 'ccdd'), TagRule.new('b', 'dd')])
=> #<struct TagRulebook ...>
>> system = TagSystem.new('aabbbb', rulebook)
=> #<struct TagSystem ...>
>> system.alphabet
=> ["a", "b", "c", "d"]

下一步，我们需要把每个字符编码成循环标签系统能使用的字符串。能让模拟工作的具体编码模式是：每个字符都表示成一个 0 组成的字符串，其长度与字母表相同，只是在某个位置上有一个 1 反映字符在字母表中的位置。10

100 和 1 的结果序列并不是二进制数，只是含有一个 1 标识特定位置的 0 组成的字符串。

标签系统字母表里有 4 个字符，所以每个字符都编码成 4 个字符组成的字符串，在不同的位置放上 1：

标签系统字符	在字母表中的位置	编码表示
a	0	1000
b	1	0100
c	2	0010
d	3	0001

为了实现这个编码模式，我们将引入CyclicTagEncoder，它可以由一个特定的字母表构造出来，然后对字母表中的字母进行编码：

class CyclicTagEncoder < Struct.new(:alphabet)
  def encode_string(string)
    string.chars.map { |character| encode_character(character) }.join
  end

  def encode_character(character)
    character_position = alphabet.index(character)
(0...alphabet.length).map { |n| n == character_position ? '1' : '0' }.join
  end
end

class TagSystem
  def encoder
    CyclicTagEncoder.new(alphabet)
  end
end

现在可以使用标签系统的 CyclicTagEncoder 对由a、b、c 和 d 组成的任意字符串进行编码了：

>> encoder = system.encoder
=> #<struct CyclicTagEncoder alphabet=["a", "b", "c", "d"]>
>> encoder.encode_character('c')
=> "0010"
>> encoder.encode_string('cab')
=> "001010000100"

使用这个编码器，我们可以把每个标签系统规则转换成对应的循环标签系统规则。我们只是对TagRule 的append_characters 进行编码，然后使用结果字符串构建一个 CyclicTagRule：

class TagRule
  def to_cyclic(encoder)
    CyclicTagRule.new(encoder.encode_string(append_characters))
  end
end

在一个 TagRule 上试一下：

>> rule = system.rulebook.rules.first
=> #<struct TagRule first_character="a", append_characters="ccdd">
>> rule.to_cyclic(encoder)
=> #<CyclicTagRule "0010001000010001">

好，append_characters 已经被转换了，但现在我们已经失去了关于哪个first_character应该触发规则的信息——不管它由哪个TagRule转换而来，每一个first_character 都会被字符 1触发。

此时，该信息由循环标签系统里规则的顺序传达：第一个规则针对字母表中的第一个字符，第二个规则针对第二个字符，以此类推。任何在标签系统中没有对应规则的字符都会在循环标签系统中得到一个空规则。

我们可以实现一个 TagRulebook#cyclic_rules 方法返回按照正确顺序排列的转换后的规则：

class TagRulebook
  def cyclic_rules(encoder)
    encoder.alphabet.map { |character| cyclic_rule_for(character, encoder) }
  end

  def cyclic_rule_for(character, encoder)
    rule = rule_for(character)

    if rule.nil?
      CyclicTagRule.new('')
    else
      rule.to_cyclic(encoder)
    end
  end
end

下面是#cyclic_rules 为我们的标签系统产生的规则：

>> system.rulebook.cyclic_rules(encoder)
=> [
#<CyclicTagRule "0010001000010001">,
#<CyclicTagRule "00010001">,
#<CyclicTagRule "">,
#<CyclicTagRule "">
]

转换后的 a 和 b规则首先出现，后边在 c 和 d 的位置上跟着两个空白规则。

这个结果与模拟工作所依托的字符编码模式相吻合。例如，如果模拟的标签系统的输入字符串是单独的一个字符 b，在循环标签系统的输入字符串中将出现 0100。以下是系统在运行这个输入时的情况：

在计算的第一步，当前规则是转换后的 a 规则，并且因为当前字符串以 0 开始，所以当前规则不会应用。但在第二步，随着前导的 0 从当前字符串中被删除，b 规则成为当前规则，同时暴露出一个前导的 1，它将触发规则应用。下两个字符都是 0，因此 c 和 d 规则都不会用到。

可见，通过小心安排输入字符串中字符 1 的出现时间，以便与循环标签系统规则出现的周期一致，我们可以在合适的时间触发合适的规则，完美地模拟常见标签系统规则的字符匹配行为。

最后，我们需要模拟原始标签系统的删除数。这可以通过向循环标签系统的规则手册中插入额外的空规则来完成，以便在一个字符被成功处理后删除合适数量的字符。如果原始的标签系统在其字母表中有 n 个字符，那么原始系统字符串的每一个字符都表示为循环标签系统字符串中的 n 个字符，因此对于每个增加的想要删除的模拟字符，需要 n 个空规则：

class TagRulebook
  def cyclic_padding_rules(encoder)
    Array.new(encoder.alphabet.length, CyclicTagRule.new('')) * (deletion_number - 1)
  end
end

标签系统的字母表里有 4 个字符，删除数是 2，因此除了已经被转换后规则删掉的字符之外，我们还需要 4 个空规则以删掉一个模拟的字符：

>> system.rulebook.cyclic_padding_rules(encoder)
=> [
#<CyclicTagRule "">,
#<CyclicTagRule "">,
#<CyclicTagRule "">,
#<CyclicTagRule "">
]

现在我们可以把所有东西都放到一起来为 TagRulebook 实现一个完整的 #to_cyclic 方法，然后在 TagSystem#to_cyclic 方法中使用它，把规则手册和当前字符串都转换成一个完整的循环标签系统：

class TagRulebook
  def to_cyclic(encoder)
    CyclicTagRulebook.new(cyclic_rules(encoder) + cyclic_padding_rules(encoder))
  end
end

class TagSystem
  def to_cyclic
    TagSystem.new(encoder.encode_string(current_string), rulebook.to_cyclic(encoder))
  end
end

下面是我们转换数字递增标签系统并运行时所发生的：

010001000100001000100001000100010001 (bbbccdddd )
10001000100001000100001000100010001
0001000100001000100001000100010001
001000100001000100001000100010001
01000100001000100001000100010001 (bbccdddd )
1000100001000100001000100010001 ➎
00010000100010000100010001000100010001
0010000100010000100010001000100010001
010000100010000100010001000100010001 (bccdddddd )
10000100010000100010001000100010001
0000100010000100010001000100010001
000100010000100010001000100010001
00100010000100010001000100010001 (ccdddddd ) ➏
0100010000100010001000100010001
100010000100010001000100010001
00010000100010001000100010001 ➐
⋮
001
01
1
➑
=> nil

➊ 标签系统的编码后版本的 a 规则在这里。
➋ 模拟字符串的第一个完整字符已经被处理了，因此下面的 4 步使用空规则删除接下来所模拟的字符。
➌ 经过循环标签系统的 8 步之后，所模拟的标签系统完成了完整一步。
➍ 编码后的 b 规则在这里触发了……
➎ ……这里又一次。
➏ 循 环 标签系统计算 24 步 了， 而我们到达了所模拟标签系统最终字符串的表示：ccdddddd。
➐ 所模拟的标签系统对于 c 或者d开头的字符串没有规则，因此循环标签系统的当前字符串持续变得越来越短……
➑ ……直到变成空字符串，然后系统停机。

这个技术可以用来模拟任何标签系统，包括本身已经模拟了一台图灵机的标签系统。这意味着循环标签系统也是通用的。