2
$\begingroup$

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?

$\endgroup$

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
0
$\begingroup$

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$.

$\endgroup$

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