3
$\begingroup$

Is the language $S = \{\langle M \rangle \mid M \text{ is a Turing Machine and } L(M) = \{\langle M \rangle\}\,\}$ decidable, recognizable and/or co-recognizable?

I tried diagonalization but can only prove that $R = \{\langle M \rangle \mid M \text{ is a Turing Machine and } \langle M \rangle \notin L(M)\}$ is not recognizable, which does not seem to help in this case...

$\endgroup$
  • 1
    $\begingroup$ I'd try a few attempts exploiting the s-m-n theorem and the 2nd recursion theorem to build quine-like TMs. It might lead to a useful m-reduction. (Why is this marked complexity-theory ?) $\endgroup$ – chi Dec 16 '15 at 20:51
4
$\begingroup$

Using the recursion theorem, for any Turing machine $T$ you can construct a Turing machine $M$ such that on input $\langle M \rangle$, $M$ executes $T$ (on the empty tape), and otherwise $M$ immediately rejects. You can use this to show that $S$ is not decidable. Using the same ideas you can explore its recognizability and co-recognizability.

$\endgroup$
  • $\begingroup$ If I understand correctly: If S is decidable, there is a decider for $S$ denoted as $H$. To obtain a contradiction, we construct a TM $B$ such that on input $w$, $B$ ignores $w$ and obtains a description of itself $\langle B\rangle$. Then $B$ run $H$ on $\langle B\rangle$. For the output, $B$ reject if $H(\langle B\rangle)$ accept and accept if $H(\langle B\rangle)$ reject. So the output of $B$ is always in contradiction with itself? $\endgroup$ – Yuanchu Dang Dec 17 '15 at 2:19
  • $\begingroup$ This is one way, though you can avoid diagonalization. $\endgroup$ – Yuval Filmus Dec 17 '15 at 5:10
  • $\begingroup$ Any thoughts on recognizability though? I suspect it is not recognizable but have no idea about its proof. $\endgroup$ – Yuanchu Dang Dec 17 '15 at 5:43
  • 2
    $\begingroup$ It's your exercise. I won't give further hints. Sometimes solving an exercise takes time. Be patient. $\endgroup$ – Yuval Filmus Dec 17 '15 at 5:45

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.