Mapping reduction to show NeverHalt is undecidable

232 Views Asked by At

I need help with showing that

$NeverHalt_{TM} = \{\langle M\rangle|M\text{ 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. Thanks for the help!

EDIT: I am reading Sipser's Theory of Computation book and the only real "strategy" is to reduce from $A_{TM}$. Perhaps he recommends this because it is a simple language, but it hampers creativity in the sense that my idea is always to reduce from $A_{TM}$ which is not always ideal.

1

There are 1 best solutions below

1
On

Assuming we know that the standard (diagonal) halting problem $H$ (and thus its complement $\overline{H}$) is undecidable:

Given the index $\langle M \rangle$, let $M^\prime$ be the machine which ignores its input and runs $M$ on input $\langle M \rangle$. Then $f$ given by $f(\langle M \rangle) = \langle M^\prime\rangle$ is computable, one-to-one, and $\langle M \rangle \in \overline{H}$ if and only if $f(\langle M \rangle) \in \text{NeverHalt}_{TM}$, thus showing that the undecidable $\overline{H}$ is $1$-reducible to $\text{NeverHalt}_{TM}$.

Note that we can't reduce $H$ to $\text{NeverHalt}_{TM}$ in this way as $\text{NeverHalt}_{TM}$ is co-c.e. (by dovetailing) and $H$ is c.e. but not computable.