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

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?

• Please edit your question to include a definition of $E_{TM}$, to make your question self-contained. Also, your title is too broad; please edit to improve it -- we have collected some advice here. Thank you! – D.W. Mar 31 '19 at 16:10
• done them both, is it okay now? – hps13 Mar 31 '19 at 17:55
• There is no many-one reduction between the two, but there many-one reductions between one of these and the complement of the other. – Yuval Filmus Mar 31 '19 at 21:05

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

• thank you very much for your explanation and the contradiction given. i am studying your answer, it is very interesting! – hps13 Apr 1 '19 at 8:25