# ETM Undecidability

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.

• Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. – Raphael Mar 1 '16 at 7:48
• 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! – Raphael Mar 1 '16 at 7:48
• @Raphael. This is almost entirely non-mathematical pseudocode. I fail to see why LaTeX would be a significant improvement here. – Rick Decker Sep 27 '16 at 0:13
• 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. – Rick Decker Sep 27 '16 at 0:17
• @RickDecker Four of six code blocks are clearly mathematical formulae. – Raphael Sep 27 '16 at 7:23

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.

• I'm sorry, why is this an answer? – Ran G. Apr 29 '16 at 2:37
• 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. – Shreesh Apr 29 '16 at 13:37
• 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? – Ran G. Apr 29 '16 at 13:42
• 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. – Shreesh Apr 29 '16 at 13:54
• OK, I missed the OP's notations. It may be helpful if the answer was more self contained. – Ran G. Apr 29 '16 at 14:09

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.