动机
Post 对应问题的一个实例由若干对有限字符串构成。问题是:能否取出由若干骨牌对组成的非空序列,将它们连接起来,使上串与下串相等。这个看似简单的相等性问题,却能编码一整个图灵机(Turing machine)的计算过程:一侧列出各个格局,另一侧列出它们的后继格局。
我们分两个阶段证明这一归约。先考虑修改版问题:它要求指定的一块骨牌必须最先使用,其初始的不匹配恰好给出机器的第一个格局。随后,通过一个标记符构造去除这一要求,得到所有骨牌字符串均非空的普通实例。
定义
定义 5.4.1
(Post 对应问题与修改版)
PCP 骨牌是有限字母表上一对非空串 。一个解是一个非空的下标序列 ,满足 。骨牌可以重复使用。修改版 PCP(MPCP)另外要求 。
定义 5.4.2
(规范化的机器与格局)
我们从确定型图灵机的接受问题出发进行归约,该问题的不可判定性已在可计算性一章中证明。这里采用标准的等价模型:带为半无限,存在一个读写头永不越过的左边界,有限的带字母表含有空白符,并且接受状态与拒绝状态是互不相同的停机状态。接受状态没有普通的转移。状态符号与带符号取自互不相交的有限字母表,分隔符与结束标记符均为全新符号。一个格局是一个有限的非空带字符串,其中恰有一个状态符号,紧挨在被扫描的带符号之前。除非需要用来表示被扫描的单元格,否则可以省略末尾的空白符。
定理
定理 5.4.3
(修改版对应问题的不可判定性)
存在一个可计算的变换,把一台机器及其输入变为一个骨牌字符串均非空的 MPCP 实例,使得该实例有解当且仅当机器接受该输入。
定理 5.4.4
(骨牌非空的 PCP 的不可判定性)
骨牌字符串均非空的 MPCP 可以有效地归约到骨牌字符串均非空的普通 PCP。因此,即使在这一非空约定下,普通 PCP 仍然不可判定。
半无限且带受保护边界的机器模型是标准的等价图灵模型;本章把这一模型等价性事实现为先修结论使用。每个状态、带符号和全新的标记符都在有限的对应字母表中编码。两个定理的证明如下:先构造骨牌,再给出正确性的两个方向,最后分析标记符变换。
证明
计算历史的骨牌
固定机器 与输入 。令 为其初始格局(若输入为空,则含一个空白符)。引入全新的分隔符 与结束标记符 ,二者均不出现在带字母表与状态字母表中。指定的首块骨牌为
它的下串比上串多出一个格局和一个分隔符。对每个带符号 加入复制骨牌 ,并加入分隔符骨牌 。不要为状态符号加入复制骨牌。
对于“在状态 下扫描 ,写入 ,进入状态 并向右移动”的转移,加入 。同时加入右边界版本 ,其中 表示空白带符号。后者在读写头移出已表示的右端时,显式地产生一个被扫描的空白符。
对于“写入 ,进入 并向左移动”的转移,对每个带符号 加入 。这使状态标记符移到前一个单元格,同时保持该单元格的符号不变。受保护的左边界约定保证合法的转移永远不需要用到左侧未表示的单元格。
对于接受状态 和每个带符号 ,加入清理骨牌 与 。最后加入结束骨牌
所有骨牌分量均非空。清理骨牌并不是机器的步骤;它们只允许在接受状态出现之后使用,并逐步删去接受状态周围的带符号。
由接受运行得到解
证明
(接受运行给出解)
使用强制的首块骨牌之后,上串为 ,下串为 。设上串已追上到某个格局 之前的分隔符,而下串还多出后缀 。对远离状态标记符的带符号使用复制骨牌,在标记符处使用一块合适的转移骨牌。于是上串追加 ,下串追加其后继格局及分隔符。
对于在已表示的右端向右移动的情形,使用边界骨牌在新状态之后追加一个空白符。对于向左移动的情形,含有前一个带符号的骨牌把状态标记符移到正确的位置。重复这一过程,就可以跟随有限的接受计算的每一步。
一旦 出现,就在相继的格局副本上使用清理骨牌,每次删去相邻的一个带符号。最终多出的格局仅剩 。结束骨牌使上串追加 ,下串追加 ,于是累积起来的两个字符串相等。
由解得到接受运行
证明
(解给出接受运行)
在任何结束骨牌之前,下串恰好比上串多一个分隔符 。第一块骨牌之后即是如此,而每块复制、转移和清理骨牌在两侧含有的分隔符个数相同。因此,没有结束骨牌就不可能相等。
标记符 只出现在结束骨牌中。在两个相等的连接串中,该标记符的首次出现必须对齐。去掉第一块结束骨牌之后的所有骨牌,得到一个以该骨牌结尾的解。在它之前,相等性迫使上串依次重现下串的初始格局块以及随后的每个格局块。
被复制的块恰含一个状态符号。由于状态符号没有复制骨牌,扫描经过该符号时必须使用机器转移骨牌或接受清理骨牌。周围的带符号与分隔符原样复制。因此,在接受之前,每个完整的下一个块都是合法的后继格局。末端的右移可以显式地加入空白符;若省略了末尾的空白符,那么除非该状态是接受状态(此时机器已经接受),否则只会在分隔符之前产生一个无法处理的状态。向左边界的移动已被规范化的机器模型排除。
清理骨牌只能在状态符号 出现之后使用。它们保留该状态并删去相邻的带符号。只有当尚未匹配的格局已被化简为 时,结束骨牌才能匹配。因此任何解都是通过一个合法的计算到达接受状态的。拒绝停机或不接受的畸形边界无法被闭合。
该构造只有有限块骨牌,并且可由 计算得出:它枚举有限的转移表和带字母表,并为每条规则写出一个有限字符串。这就证明了 MPCP 不可判定:若存在这类实例的判定器,就能判定机器是否接受。
证明透视
各项设计选择在何处被用到
论证依赖三项设计选择,每一项都在可以指出的位置被用到。第一,除首块与结束骨牌之外,每块骨牌两侧的分隔符个数相同,所以下串恒比上串多一个分隔符,任何解都无法避开结束骨牌。第二,也是最不明显的一点:不为状态符号设复制骨牌。这把看似静态的字符串相等变成一条规则:每个格局块都必须在其唯一的状态符号处被改写,于是相邻的块互为后继格局。若加入状态符号的复制骨牌,一个块便可以越过状态符号而不应用任何转移,下一个块就不再是合法的后继格局。第三,标记符 只出现在结束骨牌中,而结束骨牌要求尚未匹配的块恰为 。清理骨牌只为 而设,所以拒绝或不终止的计算无法收尾。
去除强制首块的条件
定义 5.4.5
(标记符映射与变换后的实例)
设一个 MPCP 实例在字母表 上有非空骨牌 ,并指定第一块骨牌。选取 之外的全新标记符 、 和 。对字符串 ,定义
这两个映射都保持连接运算,并且 。构造如下的普通 PCP 骨牌:
- 一块特殊起始骨牌 ;
- 对原来的每块骨牌 ,一块普通骨牌 ;
- 一块结束骨牌 。
每个分量都非空,因为原骨牌的字符串非空,而新增的标记符字符串也非空。
证明
(标记符变换下解的对应)
若 MPCP 实例有解 ,其公共连接串为 ,则依次使用特殊起始骨牌、普通骨牌 ,再用结束骨牌。上串为 ,下串为 ,二者相等。
反之,任何普通 PCP 的解必须以特殊起始骨牌开始:普通骨牌的上串以 开头而下串以原字母表中的符号开头,结束骨牌则以 与 开头;只有特殊骨牌的两侧以同一个全新标记符开头。在第一块结束骨牌之前,相等的连接串中不可能出现第二块特殊起始骨牌。每块普通骨牌在两侧各增加偶数的长度,所以在起始骨牌之后,上串前缀的长度为奇数(),下串前缀的长度为偶数()。因此第二个 会在两个字符串中出现于奇偶性相反的位置,标记符无法对齐。
相等的解必须含有结束骨牌:若没有它,按同样的计算,整个上串的长度为奇数而整个下串的长度为偶数,二者不可能相等。在第一个 处,相等性迫使
其中 分别是由第一块骨牌及随后所选的普通骨牌下标所得的上串连接与下串连接。由于 且 是单射,所以 。对应的原下标序列以第一块骨牌开始,并且解出了该 MPCP 实例。这就完成了到普通 PCP 的归约。
反例模式
去掉首块条件会改变答案
一个诱人的捷径是:对同一组骨牌直接问普通问题,以为答案与 MPCP 相同。取字母表 与骨牌 、,并指定骨牌 。以骨牌 开头的序列,上串以 开头而下串以 开头,两侧永远不会一致,所以这个 MPCP 实例无解。但作为普通 PCP 实例,单块骨牌的序列 已是解,因为 。两个答案不同,所以必须做标记符变换。变换后得到起始骨牌 、普通骨牌 与 ,以及结束骨牌 。每个解都必须以起始骨牌开头,而它的上串 与下串 在第三个符号不同,所以变换后的实例同样无解,与该 MPCP 实例一致。
例题详解
例题 5.4.6
(单个机器转移)
若 有一个右移转移:在状态 读到 ,写入 并进入 ,则骨牌 把局部格局片段 替换为 。此时状态标记符位于右侧符号之前,前提是右侧确有已表示的符号。
例题 5.4.7
(向左移动的转移)
对于读到 、写入 并进入 的左移,若前一个带符号为 ,则得到骨牌 。新的状态标记符紧接在 之前,即新被扫描的符号。
例题 5.4.8
(标记符恒等式)
对 ,有 且 。因此 。末尾的标记符 使两个错位的编码对齐。
例题 5.4.9
(单块骨牌的 MPCP 解)
若指定的骨牌是 ,则它单独就解出该 MPCP 实例。变换后的序列使用特殊起始骨牌,再用结束骨牌。其上串与下串都成为 。
例题 5.4.10
(一次完整的接受运行)
设机器只有一个转移:在状态 读到 时,写入 ,进入 并向右移动。输入为 ,所以 ,带字母表为 。用到的骨牌(写成(上串,下串))如下:
- 首块骨牌 ;
- 右边界转移骨牌 :读写头移出了已表示的右端,所以必须明确写出一个空白符;
- 复制骨牌 与 ;
- 清理骨牌 与 ;
- 结束骨牌 。
依次使用:首块骨牌、边界骨牌、、、、、、结束骨牌,则上串与下串都拼出
下串依次写出格局 、、 与 ,上串落后一个格局逐步追上,最后由结束骨牌把 与单独的 对齐。
概念视角算法
把解看成穿过“悬出部分”的路径
把两个部分连接中较长者超出较短者的部分称为悬出部分。只有当两个字符串保持一致(其中一个仍是另一个的前缀)时才可以接上一块骨牌,接上后得到新的悬出部分。于是一个解就是至少用一块骨牌、从空的悬出部分出发又回到空的悬出部分的路径。在上面完整的接受运行中,第一块骨牌之后的悬出部分是 ,边界骨牌之后是 ,而结束骨牌之后为空。
常见错误
常见错误
(以为每块骨牌自身必须平衡)
一块骨牌的上串与下串不必等长,只有在把整个非空序列连接起来之后才要求相等。计算构造有意让下串一直领先一个格局,直到结束骨牌出现。
常见错误
(随意复制状态符号)
若随意复制状态符号,则一个格局可以在不应用任何转移的情况下通过一轮扫描。状态符号只由转移骨牌或接受清理骨牌处理,这就迫使计算具有预期的结构。
总结
MPCP 骨牌在一侧编码一个格局,在另一侧编码其后继格局;接受状态使清理与闭合成为可能。错位标记符变换在普通 PCP 实例中强制使用指定的首块骨牌,并保持骨牌字符串非空。两个归约合在一起,由图灵机接受问题证明了 PCP 不可判定。
练习
快速检查
(在 MPCP 构造中,强制首块骨牌在两侧各放置了什么?)
比较这块骨牌上串与下串的内容。
解答 · 答案
上串为 ,下串为 ,所以下串领先了初始格局和一个分隔符。
快速检查
(为什么机器的状态符号没有复制骨牌?)
想一想扫描经过状态符号时允许做什么。
解答 · 答案
没有状态符号的复制骨牌,复制一个格局块就必须在其唯一的状态符号处使用转移骨牌,或在接受之后使用接受清理骨牌。这就防止了不接受的格局被原样复制并冒充为下一步。
快速检查
(验证 。)
先写出 与 。
解答 · 答案
且 ,所以 ,而 ,两侧相等。
快速检查
(为什么变换后的普通实例的解必须最先使用特殊起始骨牌?)
比较各类骨牌上串与下串的第一个符号。
解答 · 答案
普通骨牌的上串以 开头而下串以原符号开头,结束骨牌的上串以 开头而下串以 开头。只有特殊起始骨牌的两侧以同一个全新的 开头,所以只有它能开始一对相等的连接串。