关于Kozen书中停机问题归约到空串接受判定的若干疑问

我刚学这个归约的时候也绕了好久，咱们一步步把你的疑问掰开揉碎讲：

首先得先明确这个证明的核心思路：我们要证明「判定图灵机是否接受空串ε」（记为A_ε）是不可判定的，方法用的是归约法——如果A_ε是可判定的，那我们就能用它来解决已知不可判定的停机问题（HP），这就矛盾了，所以A_ε必然不可判定。这个逻辑链是整个构造的前提，先把它记牢。

你的疑问逐个解答 #

1. 为什么M'并非基于能判定ε是否被接受的实际机器？ #

这里的关键是：我们是假设存在一台能判定A_ε的机器D（只是假设！），然后用这个假设的D，搭配我们构造的M'，来造一台能解决HP的机器。M'不是判定机，它只是一个普通的图灵机——我们把M'喂给假设的D，通过D的输出反推原HP问题的答案。

换句话说，M'的作用是把「M在x上是否停机」这个HP问题，转化为「M'是否接受ε」这个A_ε问题，它是连接两个问题的桥梁，不需要自己是判定机。

2. 为什么要擦除输入y？ #

这步是为了让M'的接受行为和输入y彻底无关！不管你给M'什么输入y，它都会先把y擦掉，然后硬写入我们要测试的x，再运行M。

这样一来，M'的语言只有两种可能：

• 如果M在x上停机，那M'不管输入什么都会接受，也就是它的语言是所有字符串的集合Σ*，自然也接受ε；
• 如果M在x上不停机，那M'不管输入什么都会一直跑下去（或者拒绝），它的语言是空集，自然不接受ε。

擦除y的目的，就是把M'的语言变成「全接受」或「全不接受」，这样「M'是否接受ε」就完全等价于「M在x上是否停机」——这正是我们要的等价关系！

3. M'中的x是任意的吗？ #

不是，x是我们当前要解决的停机问题实例里的那个x。比如现在我们要判断「图灵机M在字符串x上是否停机」，这个x是固定的，我们把它硬编码到M'的有限控制器里。每个不同的HP实例（M,x），都会对应一个独一无二的M'。

4. 为什么不能用这种方法证明任意判定问题不可判定？ #

核心原因是：这个构造只适用于能和停机问题建立「等价映射」的问题，不是所有问题都能做到这一点。

举个例子：

• 如果你想证明「判定TM是否接受字符串'abc'」不可判定，确实可以用类似构造——把M'改成擦除输入后写'abc'，运行M，停机则接受，这样「M'是否接受'abc'」就等价于「M在'abc'上是否停机」，归约成立；
• 但如果是「判定TM的状态数是否大于5」这个可判定问题，你就没法用这种构造把HP归约到它——因为这个问题的答案只看TM的描述（数状态数就行），和TM的运行行为（是否在某个输入上停机）完全无关，你没法构造出一个M'，让「M在x上是否停机」等价于「M'的状态数是否大于5」。

所以这个方法不是万能的，只有当目标问题和TM的运行行为相关，且能建立「原问题成立 ↔ 目标问题成立」的双向等价关系时，才能用归约法证明不可判定。

再走一遍完整的归约逻辑，帮你串起来 #

假设存在一台判定A_ε的机器D：输入任意TM M''，输出yes如果M''接受ε，否则no。
我们构造一台判定HP的机器H，输入是(M,x)：

1. 按照教材步骤构造M'：擦除输入y → 写x → 运行M → M停机则接受；
2. 把M'输入给机器D；
3. 如果D输出yes，说明M'接受ε → 等价于M在x上停机，H输出yes；如果D输出no，H输出no。

但我们早就知道停机问题是不可判定的，所以这样的机器H不可能存在——那只能说明我们最开始的假设（存在判定A_ε的机器D）是错的，因此A_ε是不可判定的。

内容的提问来源于stack exchange，提问作者yesyes