0
$\begingroup$

This question already has an answer here:

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.

$\endgroup$

marked as duplicate by David Richerby, Discrete lizard, Evil, Yuval Filmus, vonbrand May 30 '18 at 13:56

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\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