# Prove that {⟨M,w⟩∣M accepts w only} is unrecognizable [closed]

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

• 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. – David Richerby Dec 23 '15 at 18:26
• The Rice-Shapiro theorem is very handy for this kind of questions. – 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
accept
if M(w) halts
accept


Now

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