[Solved]: Proof by Reduction: From Empty Language to Halting Problem on Empty Input

Problem Detail: 

Question: Let language $E$ = {$\langle M \rangle$ | $M$ accepts no inputs whatsoever} Let language $H$ = { $\langle M \rangle$ | $M$ halts on an empty string input}.

Is it possible to show that $H$ is undecidable by reducing $E$ to it? (You can take it as a given that we know $E$ to be undecidable.) If so, show the work. If not, explain why not.

---

My attempt:

Assume that $H$ is decidable (that there exists a Turing Machine that decides $H$) and write a subroutine that maps the input, a machine description $\langle M \rangle$, to some other machine description $\langle N \rangle$, as follows:

def $R(\langle M \rangle)$:
  def $N(x)$:
    Check whether $M$ accepts no input whatsoever.
    If so:
      accept and halt on all inputs $x$ (including when $x$ == '')
    else, if $M$ accepts some input:
     loop forever on all inputs $x$ (including when $x$ == '')
    return $\langle N \rangle$

Does the above mapping work?

The subroutine $N(x)$ completely ignores the input $x$, and first checks whether $M$ accepts nothing. IFF so, $N$ will halt on every input $x$. Otherwise, IFF $M$ accepts something, then N will loop forever on all inputs $x$.

So, IFF $\langle N\rangle$ is accepted by a decider Turing Machine as belonging to $H$ (meaning $N$ halts on all inputs, including the empty string), we know $\langle M \rangle$ is accepted as belonging to $E$ (meaning $M$ accepts nothing).

Vice versa: IFF $\langle N \rangle$ is not accepted as belonging to $H$ ($N$ loops forever on all inputs, including the empty string), we know $\langle M \rangle$ is not accepted as belonging to $E$ ($M$ accepts something).

So we have a mapping where $\langle M \rangle$ is an element of $E$ IFF $\langle N \rangle$ is an element of $H$, Thus the mapping works. A decider Turing Machine for $H$ would be able to tell the difference, thereby leading us to be able to decide $E$. But since we know a priori that $E$ is undecidable, $H$ is also undecidable.

---

I'm just getting my feet wet on mapping-reducibility and am unsure whether the above is correct. Any help would be greatly appreciated.

Asked By : user3280193

Answered By : Shreesh

See (Blank tape halting problem vs. Emptiness problem ($H_0$ vs. $E_{TM}$)).

$H$ is Turing-recognizable but not co-Turing-recognizable.

$E$ is co-Turing-recognizable but not Turing-recognizable.

Their undecidabilities are of different kind. So we need to reduce $M$ to $N$ in such a way that:

$\langle M \rangle \in E$ if and only if $ \langle N \rangle \not\in H$.

Consider the following reduction from $M$ to $N$. Turing Machine $N$ on empty input will simultaneously generate all input and run $M$ as a universal Turing Machine on that input (again simultaneously) and halts (either accept of reject, doesn't matter) if some simultaneous thread of $M$ accepts on some input. On non-empty input it does not matter what $N$ will do.

We can easily see that if $M$ does not accept anything then it implies $N$ will never halt on empty input. If $M$ accepts something then it implies that $N$ will halt on empty input.

Therefore, $\langle M \rangle \in E$ if and only if $ \langle N \rangle \not\in H$.

So, we have got a Turing reduction (in fact, a polynomial time Karp reduction).

$E \leq_M \overline{H}$

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/53501