如何证明指定语言的不可判定性？可借助A_TM、HALT_TM或E_TM

直接从**A_TM**（已知不可判定的语言，定义为A_TM = { <M, w> | M是图灵机，M接受输入串w }）归约即可，步骤如下：

1. 假设前提：先假设目标语言L是可判定的，也就是存在一个判定器R，给它输入任意<M>，它能在有限时间内告诉你M是否接受所有偶数长度的字符串。

2. 构造归约用的图灵机M'：
   拿A_TM的输入<M, w>来构造M'：

   • 当M'收到输入x时：
     • 先看x的长度是不是偶数：是奇数直接拒绝；
     • 要是偶数，就模拟M运行w：M接受w的话，M'就接受x；M拒绝w的话，M'就拒绝x。

3. 用R判定M'，反推A_TM的结果：

   • 把<M'>喂给R，如果R输出“是”，说明M'接受所有偶数长度的字符串——这只有一种可能：M接受了w（毕竟只要M接受w，所有偶长x都会被M'接受；要是M拒绝w，所有偶长x都会被M'拒绝，R就会输出“否”），那我们就知道<M, w>属于A_TM；
   • 要是R输出“否”，说明M'没法接受所有偶长字符串，那肯定是M拒绝了w，<M, w>不属于A_TM。

4. 导出矛盾：
   要是L真的可判定，那我们就造出了能判定A_TM的机器，但A_TM是公认的不可判定语言，这就矛盾了。所以L肯定不可判定。

其他归约思路 #

你想用HALT_TM或E_TM也行：

• 用HALT_TM的话，构造M'让它接受所有偶长字符串当且仅当M在w上停机，再用L的判定器反推HALT_TM的结果；
• 用E_TM的话，构造M'让它的语言为空当且仅当M不接受所有偶长字符串，反向推导矛盾就行。

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