turing-machines - 从 ATM 减少到 ATM-co

Question

从 ATM 到 ATM-complement 有减少吗？

我一直在想太多，找不到答案。

我知道从 ATM-complement 减少到 ATM 是不可能的，因为如果是这样，ATM 就不会在 RE 中。但是我怎样才能反其道而行之呢？

非常感谢 ：）

Answer 1

没有从 (A _TM ) ^c到 A _TM的映射缩减。要看到这一点，请注意 A _TM是图灵可识别的，因此如果 (A _TM ) ^c ≤ _m A _TM，我们将拥有 (A _TM ) ^c将是图灵可识别的。但这是不可能的，因为我们知道 (A _TM ) ^c不是图灵可识别的，因为如果是，A _TM将是可判定的（因为任何图灵可识别和共同图灵可识别的语言都是可判定的）。

_{但是，从 (A TM} ) ^c到 A _TM存在图灵简化。_{只需调用 A TM}的子程序并返回相反的结果。