0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.
| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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... $\endgroup$ – MercyDude May 15 at 21:38
  • $\begingroup$ 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. $\endgroup$ – Steven May 15 at 21:43
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

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.