is it possible to reduce $HALT_{TM}$ to $E_{TM}$?

Question

I am wondering, if it is even possible: is it possible to reduce $HALT_{\text{TM}}$ to $E_{\text{TM}}$?

$HALT_{\text{TM}}=\{\langle M,w\rangle\mid M\text{ is a }TM\text{ and }M\text{ halts on input }w\}$

$E_{\text{TM}} =\{\langle M\rangle\mid M\text{ is a TM and } L\left(M\right)=\emptyset \}$

I tried to look online, in summaries and handouts and even in several books (including Sipser's book), but couldn't find any indication on it.

is it possible? if so, how?

Answer 1

Nice question.

No, you cannot reduce $HALT_{\text{TM}}$ to $E_{\text{TM}}$, although you can reduce $HALT_{TM}$ to $\overline{E_{\text{TM}}}$. Here we are talking about Turing reduction.

$HALT_{\text{TM}}$ can be reduced to $\overline{E_{\text{TM}}}$

Let $\langle M,w\rangle$ be such that $M\text{ is a }TM\text{ and }M\text{ halts on input }w$. Now let us construct a TM $M'$. On an arbitrary input $u$, $M'$ will check whether $u$ is the same as $w$.

• if it is not, $M'$ will run forever.
• if it is, $M'$ will simulate $M$ on input $w$. Then once $M'$ halts, $u$ is considered as accepted.

We can make the transformation from $M$ to $M$ be algorithmic, thanks to the existence of a universal TM machine.

It is routine to verify that $\langle M,w\rangle$ is in $HALT_{TM}$ if and only if $M'$ is in $\overline{E_{\text{TM}}}$.

$HALT_{\text{TM}}$ cannot be reduced to $E_{\text{TM}}$

For the sake of contradiction, suppose $HALT_{\text{TM}}$ is reduced to $E_{\text{TM}}$ by reduction $f$. Then $\overline{HALT_{\text{TM}}}$ is reduced to $\overline{E_{\text{TM}}}$ by reduction $f$ as well. Since $\overline{E_{\text{TM}}}$ is Turing-recognizable, so is $\overline{HALT_{\text{TM}}}$. Since $HALT_{\text{TM}}$ is Turing-recognizable, we have $HALT_{\text{TM}}$ is decidable, which is known to be false, however. This contradiction shows that $HALT_{\text{TM}}$ cannot be reduced to $E_{\text{TM}}$.