# How does this reduction to prove undecidability account for epsilon?

I have the following proof that the Empty String problem:
ES = {M | M accepts $\epsilon$}
is undecidable:

$f<M,w>$ = Construct a new machine $M_2$ such that:
$M_2$ = given input x erase x from the tape and run M on w:
if M accepts w $\longrightarrow$ accept
if M rejects w $\longrightarrow$ accept
if M loops on w $\longrightarrow$ loop

I see how the function only accepts when the halting problem accepts since it only accepts when M accepts/rejects (halts). However I don't see how it only accepts when M accepts $\epsilon$ too. If for example M rejects $\epsilon$ then $M_2$ would accept since M halted on w. Wouldn't this be a flaw in the reduction? How does this reduction account for $\epsilon$?

• "[...] when M accepts ϵ too"; The input to the halting decider is not run on $\epsilon$. I'm not sure whether it's just ambiguous notation, or you got confused. Could you clarify what you mean by M in your last paragraph? Commented Feb 26, 2018 at 9:13
• @potestasity Pardon my ignorance but isn't it a halting recognizer since it loops and doesn't reject where a decider only halts and accepts or halts and rejects? For $\epsilon$, I was thinking that M is run on $\epsilon$ via w, i.e. <M, w>. So if M halts on w then it $M_2$ accepts but if $\epsilon$ is fed into M when $M_2$ is simulating it then it should accept too. There's probably something that I'm missing/confused about but don't realize. Commented Feb 27, 2018 at 1:54

Let $x = \langle M, w \rangle \in H$, where $H$ is the usual haltingproblem. Then $\langle M_2 \rangle$ halts on every input, especially on $\varepsilon$ and by construction accepts every input, especially $\varepsilon$. Hence, $f(x) = \langle M_2 \rangle \in ES$.

Now assume $x = \langle M, w \rangle \notin H$, i.e. $M$ loops on $w$. Then $M_2$ loops on every input, especially $\varepsilon$ and thus, never accepts it. $\langle M_2 \rangle \notin ES$.

• I see how $M_2$ halts on every input which includes $\epsilon$ but couldn't <M,w> when run with w=$\epsilon$ reject $\epsilon$ but since it halted then $M_2$ still accepts? I see how it halts on every input but I don't see how this means it accepts every input. What do you mean by "by construction accepts every input"? Commented Feb 27, 2018 at 1:56
• It doesn't matter what $M$ does (wrt to acceptance behavior) with $\varepsilon$. The Turing machine $M_2$ is the result of two simple transformations from $M$: 1. Delete input, write $w$ as new input and then start $M$, 2. When $M$ reaches its termination state, add another steps that fixes the output to accept, no matter what the original output of $M$ was. "By construction accepts every input" means that the transformation $f$ maps $\langle M, w \rangle$ that if $M$ halts on $w$, $M_2$ will halt (and accept) on every input. Commented Feb 27, 2018 at 13:53
• I guess I'm having trouble understanding why $M_2$ $\epsilon$ ES because it halts on every input including $\epsilon$ whereas the language of ES is only machines which accept $\epsilon$ so a machine that halts and rejects $\epsilon$ wouldn't be in ES but would be in HP and $M_2$. Also why does the value of $x$ matter when the machine just erases $x$ anyways? Commented Feb 27, 2018 at 20:25
• $M_2 \in ES$ just means that $M_2$ accepts $\varepsilon$ all other input do not matter. However, $M_2$ is constructed from a Turing machine $M$ and some word $w$ in a way that $M_2$ accepts $\varepsilon$ iff $M$ halts on $w$. This construction is actually not really profound as $M_2$ does basically the same on every input (erasing it, use $w$ as input instead, simulate $M$ on $w$, if simulation halts, accept). This means, and I guess you have not realized yet, that the output of $f$ can only be two things: Either a TM $M_2$ that computes $M_2(x) = 1$ for all $x$ or $M_2(x) = \bot$ for all $x$. Commented Feb 28, 2018 at 10:07