Mapping reduction to show NeverHalt is undecidable

Question

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.

Answer 1

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

Answer 2

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$