To show that L is not Turing-recognizable, we can use a reduction from the complement of the ATM problem (ATM'). However, I'm not sure about how we would prove that the complement of L is not Turing-recognizable. I'm wondering if we could just use the same from as for L but instead of rejecting if ATM' accepts and vice versa, but I don't understand these well enough to understand if that's feasible.

  • $\begingroup$ Hint: Are you familiar with the halting problem? $\endgroup$
    – codeR
    Commented Apr 25 at 9:13


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.