1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – Raphael Feb 23 '16 at 11:22
4
$\begingroup$

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

$\endgroup$

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.