ETM Undecidability

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

I think the issue might be in the difference between saying "M is the kind of machine that accepts $w$" and "I simulated M on w, and it accepted."

The decider $R$ does not run $M_1$ on any particular input. $R$ just (somehow!) checks whether the language of $M_1$ is empty or not.

We've defined $M_1$ so that its language will be empty if and only if $M$ is a machine that rejects $w$. We did this by having $M^\prime$ reject all strings besides $w$ right away. Then it decides whether to accept $w$ by just copying whatever $M$ does. So, if $M$ rejects $w$, then $M^\prime$ is a machine that rejects everything. If $M$ accepts $w$, then $M^\prime$ is a machine that rejects everything except for $w$.

The machine $R$ is supposed to be able to tell whether a TM is the sort of machine that rejects everything. If that were possible, you could solve the acceptance problem. Given $M$ and $w$, construct the machine $M^\prime$ that copies $M$'s behavior on $w$ and rejects all other strings. Then $M^\prime$ is the type of machine that rejects all strings if and only if $M$ is the type of machine that accepts $w$.

The decider $S$ takes in $M$ and $w$ and produces $M^\prime$. It decides whether $M^\prime$ has an empty language, which immediately tells you whether $M$ rejects $w$. If $M^\prime$ has an empty language, then $M$ rejects $w$, so respond NO—M doesn't accept w. If $M^\prime$ turns out not to have an empty language, we know it has just one string in it— w, and that can only happen if w is in the language of $M$. Respond YES—M accepts $w$.