证明语言T的不可判定性：T={<M> | 图灵机M接受w则必接受w^R}

首先明确目标语言：

T = {<M> | M是图灵机，若M接受字符串w，则必接受w的反转字符串w^R}

咱用归约法来证明——把已知不可判定的A_TM（A_TM = {<M,w> | 图灵机M接受输入w}）归约到T上，推导矛盾。

步骤1：假设T是可判定的 #

先做反证假设：存在判定器R能判定T。也就是说，给R输入任意图灵机的编码<M>：

• 若M满足T的条件（接受w就必接受w^R），R接受；
• 否则R拒绝。

步骤2：构造图灵机S，利用R判定A_TM #

我们要构造一个图灵机S，它的输入是<M,w>（A_TM的输入格式），核心是构造一个辅助图灵机Q，让R对<Q>的判定结果等价于M是否接受w。

Q处理输入字符串x的逻辑如下：

• 如果x不是01或10，直接拒绝；
• 如果x是01，直接接受；
• 如果x是10，则运行M处理w：
  • 若M接受w，Q接受x；
  • 若M拒绝w，Q拒绝x。

步骤3：分析Q与T的关系，关联到M是否接受w #

现在看两种情况：

1. 当M接受w时：
   Q接受01，同时也接受10（因为M接受w）。注意01的反转是10，10的反转是01——也就是说，所有被Q接受的字符串，它们的反转也都被Q接受，完全符合T的条件。所以R输入<Q>会接受。

2. 当M不接受w时：
   Q仍然接受01，但会拒绝10（因为M不接受w）。此时存在被Q接受的字符串01，它的反转10却不被Q接受，不符合T的条件。所以R输入<Q>会拒绝。

步骤4：完成S的逻辑，导出矛盾 #

S的完整逻辑就是：

• 输入<M,w>，构造上述图灵机Q；
• 运行R处理<Q>；
• 若R接受，S就接受<M,w>（说明M接受w）；
• 若R拒绝，S就拒绝<M,w>（说明M不接受w）。

但问题来了——A_TM是已知不可判定的，可我们居然构造出了能判定A_TM的S，这就和已知结论矛盾了。

这说明最开始的假设“T是可判定的”不成立，因此T是不可判定的。

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