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