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

Improve this question
$\endgroup$
1
  • 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
    Commented Dec 16, 2015 at 20:51

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
4
  • $\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
    Commented Dec 17, 2015 at 2:19
  • $\begingroup$ This is one way, though you can avoid diagonalization. $\endgroup$
    – Yuval Filmus
    Commented Dec 17, 2015 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
    Commented Dec 17, 2015 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
    Commented Dec 17, 2015 at 5:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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