proving $E_{TM}$ is undecidable using the halting language

Question

How to prove that:

$E_{TM} = \{\langle M\rangle\mid M \ is\ a\ TM\ and\ L(M)=\emptyset\}\notin R$ (is undecidable)

using the language:

$H_{halt}=\{(⟨M⟩,w):M\ halts\ on\ w\}$.

I tried to prove by contradiction that assuming $E_{TM}\in R$ I have a Turing machine which decides $E_{TM}$ and to construct with it a turing machine which decides $H_{halt}$ but I don't know how to do so.

Answer 1

Suppose that there is a Turing machine $T$ that decides $E_{TM}$.

Given a turning machine $M$ and an input $w$ you can construct a new Turing machine $M^*$ that decides whether $(M,w) \in H_{halt}$. $M^*$ operates as follows:

• It first constructs a new Turing machine $M'$ that ignores its input, simulates $M$ on input $w$ and, once the simulation is complete, accepts.
• It simulates $T$ with input $M'$ to decide whether $M' \in E_{TM}$.
• If $M' \in E_{TM}$ then $M'$ does not accept any input, which implies that $M$ cannot halt on input $w$. In this case $M^*$ rejects.
• If $M' \in E_{TM}$ then $M'$ accepts at least one input (and hence all inputs), meaning that $M$ must halt on input $w$. In this case $M^*$ accepts.

Answer 2

You are right, assuming $E_{TM}\in R$ you have Turing machine $T$ which decides $E_{TM}$ and you can construct with it a Turing machine which decides $H_{halt}$:

If we have $T$ which decides $E_{TM}$ and suppose we want to decide whether $M$ halts on $x$. Construct a Turing Machine $T_{M,x}$ which irrespective of its input $y$ simulates $M$ on input $x$: if the simulation halts (and $M$ either accepts or rejects $x$), then $T_{M,x}$ accepts its input, otherwise, it never halts.

You can convince yourself that if $M$ halts on $x$, then $L(T_{M,x}) = \Sigma^*$, and if it doesn't then $L(T_{M,x}) = \phi$.

Now you can figure out why this acts as a decider for the Halting problem.