# Prove that a language is undecidable by reducing HALT to it [duplicate]

Let

$L = \left\{ \langle \alpha, x\rangle \mathrel{}\middle|\mathrel{} \textrm{x is the only string accepted by}\mathrel{}M_\alpha \right\}$

and

$HALT = \left\{ \langle \alpha, x\rangle \mathrel{}\middle|\mathrel{} M_\alpha \mathrel{} \textrm{halts on input x} \right\}$

How can I prove that $L$ is undeciable by reducing $HALT$ to it?

I appreciate the fact that similar proofs use the fact that if we could decide $L$, then we could compute $HALT$ as a way to prove contradiction, but I don't understand how $L$ and $HALT$are related and how we can prove that one is not decidable ($L$) by saying that, by nature, the other one ($HALT$) is not.

• @PeterTaylor Yes, sorry, this is fixed now :-) – Pierre Pasquet May 25 '18 at 9:04
• Hint: Given $M_\alpha$, construct another machine $M'_\alpha$ which behaves the same on $x$ but (possibly) differently on all other inputs. – Yuval Filmus May 25 '18 at 11:46