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?

  • $\begingroup$ 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! $\endgroup$ – D.W. Mar 31 '19 at 16:10
  • $\begingroup$ done them both, is it okay now? $\endgroup$ – hps13 Mar 31 '19 at 17:55
  • 1
    $\begingroup$ There is no many-one reduction between the two, but there many-one reductions between one of these and the complement of the other. $\endgroup$ – 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}}$.

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

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.