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.
1
-
$\begingroup$ Suppose that some machine $A$ recognizes $L$. Can you determine whether or not $\langle A\rangle$ is in $L$? $\endgroup$– Yonatan NMay 7, 2021 at 4:39
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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