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

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