Show that the language L = {<M>| M is a TM and does not accept <M>} is not Turing-recognizable.

Note: Prove by contradiction. No need for reduction.

This is the problem I am trying to solve. I'm confused on how to do this without using reduction.

  • $\begingroup$ Suppose that some machine $A$ recognizes $L$. Can you determine whether or not $\langle A\rangle$ is in $L$? $\endgroup$
    – Yonatan N
    Commented May 7, 2021 at 4:39

1 Answer 1


Let's suppose that the language $L$ is decidable, so then exists a Turing Machine $M'$ such that $M'$ stops for all inputs (doesn't loop infinitely) and that $L(M') = L $.

If $\omega$ is the codification for $M'$, What happens with $M'$ with input $\omega$?

$M$' accepts $\omega$, if and only if, (as $\omega$ encodes $M'$), $M'$ does not accept $M'$, a contradiction.

This is the same idea to prove undecidability of the Halting problem and numerous other results, the idea of diagonalization


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.