3.18

规约

从停机问题规约到 Post Correspondence Problem，叹为观止，习题 5.21 进一步从 PCP 问题规约证明 CFG 的模糊性不可判定，更显理论精妙。

遗憾是 5.21 的提示给得太多，读完提示就知道了做法。实际上，提示使用 PCP 问题规约就恰到好处。好在 5.33 算是给了一次设计 CFG 的机会，恰巧参考的答案在这题上是胡扯，故快乐写题解

莱斯定理的证明也很有意思。最初的朴素想法是：从 $A_{TM}$ 规约，根据 $M$ 在 $\omega$ 上运行结果不同而在两个图灵机中选择一个模拟。然而，$M$ 可能不停机，所以这个办法不可行。解决这个问题的办法，也是证明的核心难点，就是把空语言作为其中一个语言，这不需要图灵机来模拟，直接拒绝一切即可！