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

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.

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.
• In the two last points when you say accept or reject, do you mean that $M'$ should accept/reject, if so, it seems like $M'$ uses $T$ within it's definition, isn't it a circular definition of $M'$? also in your last point it should be not in I guess... – MercyDude May 15 at 21:38
• No, I mean that the Turing the machine that we are defining (the one that constructs $M'$ and makes use of $T$) should accept/reject. This Turing machine is the one that solves the halting problem. I have edited the answer to give the name $M^*$ to this Turing machine. – Steven May 15 at 21:43

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.