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


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

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