4
$\begingroup$

How can I prove that the language $L=\left\{\langle M\rangle\mid L(M)=\left\{\langle M\rangle\right\}\right\}$ is not decidable?

When trying to use a diagonal argument, I cannot conclude from $L(M)\ne\left\{\langle M\rangle\right\}$ that $\langle M\rangle\not\in L(M)$.

Also, it seems that I cannot apply Rice's theorem because I can't say anything about the machines' encodings $\langle M\rangle$ in the definition of the set $\mathcal{S}$.

Is there an easy reduction to a known undecidable language?

$\endgroup$
  • $\begingroup$ Try using the recursion theorem. $\endgroup$ – Yuval Filmus Nov 27 '16 at 10:54
  • $\begingroup$ @YuvalFilmus I haven't learned about this in my lecture. Would you mind explaining? I believe however that there should also be a solution without the theorem. $\endgroup$ – pascalhein Nov 27 '16 at 11:06
  • $\begingroup$ Perhaps your textbook contains some information on the recursion theorem. I find it somewhat hard to believe that you can avoid ideas similar to the recursion theorem. $\endgroup$ – Yuval Filmus Nov 27 '16 at 11:57
4
$\begingroup$

The recursion theorem states that a Turing machine can get its own description on to its tape. In fact, there is a simple reduction from the acceptance problem (ATM) to this problem.

Assume $L$ is decidable. Suppose I am asked whether a TM $M$ accepts $w$. I will construct a machine $M'$ which on input $x$ checks if $x=\langle M' \rangle$. If it is not $\langle M' \rangle$ it simply rejects $x$. Otherwise it simulates $M$ on $w$, and if $M$ accepts $w$ then $M'$ accepts $x$. So $L(M') = \{ \langle M' \rangle \}$ iff $M$ accepts $w$. Hence we can pass this $M'$ as input to the decider $L$ and obtain answer for "$M$ accepts $w$?". But we know that ATM is undecidable, hence $L$ must be undecidable.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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