$$L = \{\langle M,w\rangle \mid \text{\(M\) accepts \(w\) only}\}$$ How can I prove this language is unacceptable (unrecognisable)? I think I should use a reduction, I'm not sure how.


closed as unclear what you're asking by Evil, Tom van der Zanden, David Richerby, Yuval Filmus, vonbrand Dec 25 '15 at 15:47

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    $\begingroup$ What did you try? Where did you get stuck? We're happy to help you with conceptual questions but just answering exercises for you is unlikely to help you understand. $\endgroup$ – David Richerby Dec 23 '15 at 18:26
  • 1
    $\begingroup$ The Rice-Shapiro theorem is very handy for this kind of questions. $\endgroup$ – chi Dec 24 '15 at 9:51

Let $A_w=\{\langle\,M\,\rangle\mid L(M)=\{w\}\}$ and $\mathrm{HALT}=\{(\langle\,M\,\rangle, w)\mid M\text{ halts on }w\}$. It's known that the complement, $\overline{\mathrm{HALT}}$, is unrecognizable, so if we could establish a mapping reduction $\overline{\mathrm{HALT}}\le A_w$, we'd have shown $A_w$ is unrecognizable. Since mapping reducibility is closed under complements, we'll show that $\mathrm{HALT}\le \overline{A_w}$, where, of course, $\overline{A_w}=\{\langle\,M\,\rangle\mid L(M)\ne \{w\}\}$.

Define the mapping $f: (\langle\,M\,\rangle, w)\longrightarrow \langle\,N\,\rangle$ where

N(x) =
   if x = w
   if M(w) halts


  • If $(\langle\,M\,\rangle,w)\in \mathrm{HALT}$ we'll have $L(N)=\Sigma^*$ so $\langle\,N\,\rangle\in \overline{A_w}$
  • If $(\langle\,M\,\rangle,w)\notin \mathrm{HALT}$ we'll have $L(N)=\{w\}$ so $\langle\,N\,\rangle\notin \overline{A_w}$ Thus establishing the reduction we need.

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