This question already has an answer here:

I am trying to prove that $L = \{\langle M \rangle \mid L(M) = \{\langle M \rangle \}\}$ is undecidable, where $\langle M \rangle$ is the code of the TM $M$, and $L(M)$ the language recognized by $M$.

I think I can't use Rice's theorem, so I tried to find a reduction. The halting problem for example does not help me in this case. Do you have any idea how to prove it?


marked as duplicate by Apass.Jack, Evil, David Richerby, Yuval Filmus turing-machines Feb 2 at 9:49

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Are you familiar with the recursion theorem? $\endgroup$ – Yuval Filmus Feb 1 at 17:24
  • $\begingroup$ unfortunately not $\endgroup$ – Marc Feb 1 at 17:40

The recursion theorem states that if $A(x,y)$ is a two-input Turing machine then there is a Turing machine $M$ such that $M(x) = A(x,\langle M \rangle)$. Moreover, $M$ can be constructed from $A$ effectively (i.e., using an algorithm). Using this, we can reduce the halting problem to your problem. Given a Turing machine $B$ and an input $z$, construct a new Turing machine $A(x,y)$ which acts as follows:

  • If $x = y$ then simulate $B$ on $z$.
  • Otherwise, enter an infinite loop.

Use the recursion theorem to construct a new machine $M$ that on input $x$ acts as follows:

  • If $x = \langle M \rangle$ then simulate $B$ on $z$.
  • Otherwise, enter an infinite loop.

Then $M \in L$ iff $B$ accepts $z$.


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