1
$\begingroup$

I need help with showing that $$NeverHalt_{TM} = \{\langle M\rangle \mid \text{$M$ is a TM which runs forever on every input $w$}\}$$ is undecidable by giving an explicit mapping reduction.

To show that a language reduces to any other language we must show that yes-instances are mapped to yes-instances and no-instances are mapped to no instances. We need to find a TM whose language will "help" us solve $NeverHalt_{TM}$, given $\langle M\rangle$.

I am not really sure where to go from here or in general how to proceed with undecidability problems.

$\endgroup$
2
$\begingroup$

You will not prove that $NeverHalt_{TM}$ is undecidable by "finding a TM whose language will "help" us solve" it. This would actually prove the opposite, if $M$ is a TM deciding some language.

You have to suppose $NeverHalt_{TM}$ to be decidable by a turing machine $D$, and show that with its help you can decide other non-recursive language. In other words, you have to pick a suitable undecidable language and reduce it to $NeverHalt_{TM}$. There is a reduction from the emptiness problem for turing machines : $E_{TM} = \{\left < M \right >\ :\ \mathcal L(M) = \varnothing \}$.

$\endgroup$
1
$\begingroup$

You can reduce the $MP= \{\langle M,w \rangle : w \in L(M)\}$ to $NeverHalt$

For a given string $\langle M,w \rangle $ you construct the following machine $F$:

For input x:
  Simulate M for input w
    if it accepts, loop
    if it rejects accept x

Now you can see that $\langle M,w \rangle \in MP \iff \langle F \rangle \in NeverHalt$

$\endgroup$
  • $\begingroup$ This only proves that NeverHalt is undecidable if we assume that MP is undecidable -- is it? (Of course it is, but still.) $\endgroup$ – Raphael Feb 2 '14 at 22:15
  • $\begingroup$ If we want to prove it by a mapping reduction don't we have to have a known undecidable language first? since that was the question I considered it known... $\endgroup$ – lea Feb 3 '14 at 20:26
  • 1
    $\begingroup$ That's true, and a ficklish issue. Usually, every course/book has its "toolbox" of undecidable, un-semi-decidable, NP-complete, ... problems that can be used for reduction. There are few generally present defaults (afaict) so we usually fall back to the Halting problem and its complement. (Your MP is fine in the context of material that establishes that the word problem is undecidable for type-0 grammars.) $\endgroup$ – Raphael Feb 3 '14 at 21:13

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.