从字符串替换到图灵机：A=B 的完备性构造

0. 背景：A=B 是什么

A=B 是在一款解谜游戏中引入的一种极简编程语言。它的语法只有一种形式：

A = B

含义是“在字符串中找到子串 A，并把它替换为 B”。程序运行过程如下：

  1. 从输入串开始；
  2. 逐条检查规则，从第一条规则开始，寻找第一个匹配的左部；
  3. 一旦找到，就立即执行替换；
  4. 然后从头再来（回到规则表开头）；
  5. 如果没有任何规则可用，则程序停机，并输出当前字符串。

在游戏后期，会出现扩展关键字（如 (start) 匹配开头、(end) 匹配结尾、(once) 限制只替换一次、(return) 表示立即输出并停机），它们能让表达力更强。但关键是：即使完全不依赖这些扩展，A=B 也已经足够强大，可以达到图灵完备性。

什么是“图灵完备”？

图灵完备表示该系统能模拟任意图灵机：只要时间与存储足够，任何可计算的算法都能实现。直观地，它意味着：

  • 能够存储和操作任意量的信息；
  • 能够分支（条件判断）；
  • 能够循环（无限计算，直到停机）。

证明 A=B 图灵完备，就是证明它并非“替换小游戏”，而是具备通用计算能力的编程语言。

1. 理论背景：字符串重写系统为何图灵完备？

早在 20 世纪初，数学家 Axel Thue 就提出了字符串重写系统（Thue system），研究如何通过规则替换来生成和变换字符串。后来，Emil Post 进一步发展出 Post 规范系统，并证明这类系统足以表达任意可计算过程。

核心结论是：半 Thue 系统（Semi-Thue system，即字符串重写系统）能够模拟任意图灵机。其思路是将“图灵机的一个配置（状态 + 带子内容）”编码成一个字符串，再用重写规则逐步执行机器的转移函数。

下面是维基百科条目给出的一个标准构造：

  • 用字母表中的若干符号表示带子符号（\(S_k\)）；

  • 用一个唯一的状态标记（\(q_i\)）表示当前机内状态，并保证它在配置中恰好出现一次。其右侧符号即为当前读头所在位置的带子符号；

  • 向右移动的转移
    在图灵机里，“向右移动” 的意思是：读写头在处理完当前位置后，把读写位置移动到右边的一个格子。

$$ \delta(q_i, S_k) = (q_j, S_l, \rightarrow) $$

对应的重写规则是

$$ q_i S_k \to S_l q_j $$

解释：

  • \(\delta\)：转移函数；
  • \(q_i\)：当前状态；
  • \(S_k\)：当前读到的符号；
  • \(S_l\)：要写回去的新符号；
  • \(q_j\)：更新后的状态；
  • \(\rightarrow\)：表示读头右移；

  • 规则的含义是：把「状态 + 符号」替换为「新符号 + 新状态」，等价于完成写入并把状态标记移动到右边。

  • 向左移动的转移
    在图灵机里，“向左移动” 的意思是：读写头在处理完当前位置后，把读写位置移动到左边的一个格子。

$$ \delta(q_i, S_k) = (q_j, S_l, \leftarrow) $$

对应一簇规则（需对左邻符号 \(S_p\) 枚举）：

$$ S_p q_i S_k \to q_j S_p S_l $$

解释：

  • 当读头左移时，必须知道左边的符号 \(S_p\)；
  • 左邻符号 + 状态标记 + 当前符号，一起被替换成「新状态 + 左邻符号 + 新符号」；

  • 这使得状态标记成功左移，同时完成写入操作。

  • 无限带子的处理
    为了模拟“无限长”的带子，需要在两端加哨兵符号 \(h\)，并加入特殊的延展规则，使得机器在靠近边界时可以“创造”新的空白格子，从而对应无限内存的假设。

由于每次重写都必须包含且仅包含一个 \(q_i\)，所以在任意时刻都只有唯一可用的匹配位置。整个替换过程严格对应图灵机的一步步执行。因此，字符串重写系统具备完整的计算能力，也就是图灵完备。

2. 核心命题与证明纲要（把任意图灵机编译成 A=B 程序）

命题. A=B（即使不用任何关键字）也是图灵完备的。

证明思路（构造式归约）
给定任意一台确定性的单带图灵机：

$$ M = (Q, \Gamma, \sqcup, \delta, q_0, q_{\text{halt}}) $$

解释：

  • \(Q\)：有限的状态集合；
  • \(\Gamma\)：带子符号集合；
  • \(\sqcup\)：空白符；
  • \(\delta\)：转移函数，定义“遇到某符号时怎么写、状态怎么变、头怎么动”；
  • \(q_0\)：初始状态；
  • \(q_{\text{halt}}\)：停机状态。

构造一组 A=B 规则，使其在任意初始输入编码上逐步等价地重写到 \(M\) 的后续配置，直到停机。

  1. 编码配置
    用字符串来编码一台机器的状态：
$$ h , L , q_i , R , h $$

解释：

  • \(L\)：读头左边的带内容；
  • \(R\)：读头当前位置以及右边的内容；
  • \(q_i\)：当前状态，只出现一次；
  • 两端的 \(h\) 是哨兵，确保机器永远不会“掉出带子”。
  1. 生成规则
    对每条转移 \(\delta(q_i,S_k) = (q_j,S_l,\text{dir})\)，生成对应的 A=B 规则：

  • 右移：

    $$ q_i S_k \to S_l q_j $$

  • 左移（对所有 \(S_p \in \Gamma\)）：

    $$ S_p q_i S_k \to q_j S_p S_l $$

  • 遇到带子右端（\(S_0=\sqcup\)）：

    $$ h q_i S_k \to h q_j S_0 S_l $$

如果进入停机状态 \(q_{\text{halt}}\)，没有进一步规则匹配，程序就自然停机。即使没有 (return)，停机时当前字符串就是输出。

  1. 正确性
    * 唯一匹配位置：每个串里只有一个 \(q_i\)，所以只有一个规则能触发；这与 A=B 的“从左到右、按顺序找”完全兼容。
    * 一步对应：每条替换规则严格模拟图灵机的一步（写入、移动、更新状态）。
    * 停机：进入 \(q_{\text{halt}}\) 后没有规则匹配，A=B 程序停机。

因此，A=B 可以模拟任意图灵机，所以它是图灵完备的。 \(\square\)

3. 举例：计数器程序（用例证法说明完备性）

上节我们给出了严格的归约证明，这里再展示一个具体程序：

把输入的二进制数（\(1 \leq n \leq 63\)）转换成对应数量的 a

程序规则

0 = $X$
1 = $Y$
$$ =
YXXXXX$ = XXXXX$aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
YXXXX$ = XXXX$aaaaaaaaaaaaaaaa
YXXX$ = XXX$aaaaaaaa
YXX$ = XX$aaaa
YX$ = X$a
Y$ = X$a
$X =
$ =

与图灵机构造的对应关系

  1. 字母表（Alphabet）
    • 符号集合 \(\Gamma\)：0,1,X,Y,$,a。
    • 就像图灵机带子上的有限符号集。
  2. 状态（States）
    • 在一般构造中，状态由 \(q_i\) 标记。
    • 在这里，「状态」由当前匹配的模式体现：
      • 匹配 YXXX$ = “状态 = 等待展开 8 个 a”；
      • 匹配 YX$ = “状态 = 等待展开 2 个 a”。
    • 所以规则本身就扮演了转移函数 \(\delta\)。
  3. 读写头（Head）
    • 在 A=B 里没有显式的“头”，但每次替换只能在一个匹配窗口里发生：
    • 例如 YXXX$ → XXX$aaaaaaaa：可以看成读写头在 Y 上，读到右边 3 个 X 和 $，然后写出 a 并右移。
    • 例如 YX$ → X$a：可以看成读写头在 Y 上，它左边的 X 会被保留，头位置连带移动到右边继续展开。
  4. 右移的体现
    • 替换 YXXX$ → XXX$aaaaaaaa：
    • 相当于图灵机在 Y 所在格写入若干 a；
    • 然后状态标记（匹配窗口）自动“滑到右边的 $”处，继续执行。
    • 这对应于「写入后头向右移」。
  5. 左移的体现
    • 在展开尾部规则 Y$ → X$a 中：
      • 当 Y 已经贴近 $ 时，替换会把 $左边的 X 替出来，并在 Y 的左边补上 a；
      • 这等价于把读写头往左看一格，再进行展开。
    • 整个效果就和「写入后头左移」一致。
  6. 带子与哨兵（Tape & Sentinel）
    • 符号 $ 就是带子的边界标记；
    • 末尾两条规则会逐步清理辅助符号，等价于无限带的“空白格”处理。
$X =
$ =

为什么这个例子能说明图灵完备性？

  • 存储：输入二进制串被转写成 Y/X/$ 的带子配置。
  • 分支：不同的规则（YXXX$, YXX$, YX$, …）体现条件分支。
  • 循环：展开过程需要不断触发相同的规则，直到消耗完所有 Y，体现迭代。
  • 左/右移动：匹配窗口的替换效果对应于头在带子上左右移动。
  • 停机：当所有符号都归约成 a，再无规则可用时，程序自然停机。

所以，这个计数器程序已经在完整地模拟图灵机的运行：

  • 字母表 → {0,1,X,Y,$,a}；
  • 状态 → 匹配模式决定；
  • 读写头 → 当前匹配窗口位置决定；
  • 左右移动 → 替换结果把窗口推到左/右；
  • 停机 → 无规则可用。

这说明 A=B 并非“看似字符串替换”，而是真正能模拟一台图灵机。

4. 顺序/左端优先会不会削弱能力？

不会。因为在构造中我们保证了唯一状态标记 \(q_i\)：

  • 每条规则都包含且仅包含一个 \(q_i\)；
  • 串中也只有一个 \(q_i\)；
  • 因此始终只有唯一匹配。

所以，不管是左端优先还是其他策略，运行轨迹都是唯一的，能力不受影响。

5. 关系图（理论坐标系）

  • A=B：一个带优先级与锚点关键字的字符串替换语言。
  • Semi-Thue / SRS：字符串重写系统，图灵完备。
  • Post 规范系统：可化归为 SRS，同样图灵完备。
  • Thue 语言：非确定性重写为核心的怪诞语言，图灵完备。

6. 结语

  • 形式化：任意图灵机都能编译成 A=B 规则，逐步等价执行 → 图灵完备。
  • 直观例子：A+B 展现了进位传播，A–B 展现了借位传播；它们分别是算术电路的基石，而算术电路+控制逻辑=通用机。

因此，A=B 不只是一个小游戏，而是一个极简却图灵完备的语言。

p.s. 一些参考解法

Comments

comments powered by Disqus