0
$\begingroup$

I'm having trouble convincing myself of the proof for the following theorem:

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

I think I understand why we reduce $A_{TM}$ to this problem, where $A_{TM} = \{\langle M, w\rangle\mid M$ is a TM and $M$ accepts $w\}$, but here is where I get lost. We create a modified TM $M_1$ such that:

$M_1=$ "On input $x$:

  1. If $x\neq w$, reject.
  2. If $x = w$, run $M$ on input $w$ and accept if $M$ does."

and consequently create a TM $S$ that decides $A_{TM}$:

$S=$ "On input $\langle M, w\rangle$, an encoding of a TM $M$ and a string $w$:

  1. Use the description of $M$ and $w$ to construct the TM $M_1$ just described.
  2. Run $R$ on input $\langle M_1\rangle$.
  3. If $R$ accepts, reject; if $R$ rejects, accept."

My issue here lies with line 3 of TM $S$. If $R$ accepted, then we must have had $x = w$ and $L(M) = \emptyset$, and $S$ would have rejected. Likewise, if $R$ rejected, then we must have had $x\neq w$ (where $x$ could be any string but $w$). Yet $S$ would accept this, even though the 'goal' for $S$ was to accept string $w$. Can someone show me how to think about this correctly? It would be very much appreciated.

$\endgroup$
  • 1
    $\begingroup$ Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. $\endgroup$ – Raphael Mar 1 '16 at 7:48
  • 1
    $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Mar 1 '16 at 7:48
  • $\begingroup$ @Raphael. This is almost entirely non-mathematical pseudocode. I fail to see why LaTeX would be a significant improvement here. $\endgroup$ – Rick Decker Sep 27 '16 at 0:13
  • 1
    $\begingroup$ You haven't specified what $R$ is, leaving us to puzzle out what it is from context. Yes, it's not hard, but it would be better if you simply leveled out that speedbump. $\endgroup$ – Rick Decker Sep 27 '16 at 0:17
  • $\begingroup$ @RickDecker Four of six code blocks are clearly mathematical formulae. $\endgroup$ – Raphael Sep 27 '16 at 7:23
1
$\begingroup$

The approach is a little different from usual reduction is because $A_{TM}$, the accepting language, is RE and $E_{TM}$, the empty language, is co-RE.

Therefore we need to reduce $A_{TM}$ instance to $E_{TM}$ instance in such a way that

$\langle M,w \rangle \in A_{TM}$ iff $M_1 \not\in E_{TM}$

We construct $M_1$ from $\langle M,w \rangle$ as follows:

$M_1$:
Input: $x$
If $x\neq w$ then reject
else if $x=w$ then Run Universal TM on $\langle M,w \rangle$ and accept if $M$ accepts $w$ (i.e. output the answer of Universal TM).

Step 1 of the Turing Machine $S$ does exactly the reduction from $\langle M,w \rangle$ to $M_1$.

We prove by contradiction that $E_{TM}$ is undecidable. Assume $E_{TM}$ is decidable by a Turing machine $R$. Then we can show that $A_{TM}$ is decidable by reducing an instance $\langle M,w \rangle$ of $A_{TM}$ to instance $M_1$ of $E_{TM}$, get an answer using $R$ on $M_1$ and then flip the answer. But $A_{TM}=L_u$, the universal language, is undecidable. Hence by contradiction $E_{TM}$ is undecidable.

Turing Machine $R$ is used (in OP's description) to tell that if there is a Turing Machine $R$ which decides $E_{TM}$ then we can use it to decide $A_{TM}$. And since we know that $A_{TM}$ is undecidable, surely we can't have such an $R$ and therefore $E_{TM}$ is undecidable too.

Turing machine $S$ (again in OP's description) is a machine that decides $E_{TM}$ if there is an availability of Turing machine $R$ that decides $A_{TM}$ by flipping the answer.

$\endgroup$
  • $\begingroup$ I'm sorry, why is this an answer? $\endgroup$ – Ran G. Apr 29 '16 at 2:37
  • $\begingroup$ We prove by contradiction. Assume $E_{TM}$ is decidable. Then we can show that $A_{TM}$ is decidable by reducing an instance $\langle M,w \rangle$ of $A_{TM}$ to instance $M_1$ of $E_{TM}$, get an answer and then flip it. But $A_{TM} = L_u$, the universal language is undecidable. Hence by contradiction $E_{TM}$ is undecidable. $\endgroup$ – Shreesh Apr 29 '16 at 13:37
  • $\begingroup$ I don't understand. Can you specify the reduction: what is S (formally), and what is R? Flipping the answer of $A_{TM}$ doesn't necessarily give $E_{TM}$, right? $\endgroup$ – Ran G. Apr 29 '16 at 13:42
  • $\begingroup$ I used the definition of $S$ given by OP. He is confused by $R$ and has not specified what $R$ is. $R$ is the machine that decides $E_{TM}$ if we assume that $E_{TM}$ is decidable for the sake of contradiction. Step 1 of $S$ is the reduction as given by OP. Step 2 is running $R$ on input $f(x) = M_1$ and Step 3 is flipping the answer. $\endgroup$ – Shreesh Apr 29 '16 at 13:54
  • $\begingroup$ OK, I missed the OP's notations. It may be helpful if the answer was more self contained. $\endgroup$ – Ran G. Apr 29 '16 at 14:09
1
$\begingroup$

In answer to your question about line 3 of the description of $S$, let's first clarify things a bit: we assume there is a decider, $R$, for $E_{TM}$ and we use this to build a decider, $S$, for $A_{TM}$ (thus eventually establishing that such an $R$ is impossible).

With that out of the way, your question is about what happens when $R$ accepts $\langle M_1\rangle$:

  1. Since $R$ was assumed to be a decider for $E_{TM}$, $R$ accepts $\langle M_1\rangle$ if and only if $L(M_1)=\varnothing$.
  2. From the way $M_1$ was constructed, that can happen only if $M$ doesn't accept $w$ (since $M_1$ rejects everything else),
  3. So $R$ will accept $\langle M_1\rangle$ only if $\langle M, w\rangle\notin A_{TM}$.

Similarly,

  1. $R$ will reject $\langle M_1\rangle$ iff $L(M_1)\ne\varnothing$,
  2. And that can only happen when $M$ accepts $w$,
  3. And hence $R$ will reject $\langle M_1\rangle$ only if $\langle M, w\rangle\in A_{TM}$.

Finally, since $S$ was designed to do the opposite of what $R$ does, we've constructed a decider for $A_{TM}$, which of course is a contradiction, so $E_{TM}$ must be undecidable.

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