0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ "[...] 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? $\endgroup$ – potestasity Feb 26 '18 at 9:13
  • $\begingroup$ @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. $\endgroup$ – Paradox Feb 27 '18 at 1:54
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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"? $\endgroup$ – Paradox Feb 27 '18 at 1:56
  • $\begingroup$ 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. $\endgroup$ – ttnick Feb 27 '18 at 13:53
  • $\begingroup$ 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? $\endgroup$ – Paradox Feb 27 '18 at 20:25
  • 1
    $\begingroup$ $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$. $\endgroup$ – ttnick Feb 28 '18 at 10:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.