Why is this undecidability proof for $E_{TM}$ valid?

Question

I understand what it means to reduce a problem and how this is used to show by contradiction that the theorem is true.

Question What troubles me is the way the proof is formulated. In step 1.2 it is not defined what will happen if it does not accept. Wouldn't this mean that $M_1$ would run indefinitely for words not accepted by $M$? Furthermore, wouldn't this cause S to not be a decider but rather a recogniser?

Proof The proof is by contradiction. Assume that $E_{TM}$ (Empty turing machines) is decidable. Then there is a TM $M_E$ that decides it. We construct a TM S as follows:

S = On input ⟨M,w⟩ where M is a TM and w a string:

1. Construct a TM $M_1$ as follows:
   $M_1$ = On input x:
   1.1 If $x \neq w$, reject.
   1.2 Run M on input w and accept if M does.
2. Run $M_E$ on input ⟨$M_1$⟩.
3. If $M_E$ accepts, reject; if $M_E$ rejects, accept.

Clearly, S decides $A_{TM}$ . That’s a contradiction. So $E_{TM}$ is undecidable.

Answer 1

One idea for $S$ is to execute $M_E$ on $\langle M\rangle$. If $M_E$ accepts $\langle M\rangle$ then $L(M)=\emptyset$, so $M$ surely doesn't accept $w$. If $M_E$ rejects $\langle M\rangle$ all we know is that $L(M)\neq\emptyset$, i.e. that $M$ indeed does accept some string. We don't know if $M$, in particolar, accepts $w$. So the idea is to modify $M$ (into $M_1$) such that $M_1$ immidiately rejects all the strings $x$ that are not $w$, while on $w$ it just works like $M$. In this way either $L(M_1)=\emptyset$ or $L(M_1)=\{w\}$. Since $L(M_1)$ is the set of strings accepted by $M_1$, the fact that $L(M_1)=\emptyset$ tells us that there's no string accepted by $M_1$. But, and this is the crucial observation to answer your question, to not accept a string does not mean to reject. In fact a Turing machine running on a string can: accept, reject or run forever. So, the "negation of accepting a string" is "rejecting or running on it forever". This tells us that:

1. $L(M_1)=\emptyset$ if and only if $M_1$ does not accept any string, which is equivalent to say that $M$ rejects or runs indefinitely on $w$
2. $L(M_1)\neq\emptyset$ if and only if $L(M_1)=\{w\}$, which is equivalent to say that $M$ accepts $w$

At this point let's execute $M_E$ on $\langle M_1\rangle$: $$M_E(\langle M_1\rangle)=\begin{cases}\text{accept}\:\Longleftrightarrow\:L(M_1)=\emptyset\:\Longleftrightarrow\:M \text{ rejects or runs indefinitely on } w\\\text{reject}\:\Longleftrightarrow\:L(M_1)\neq\emptyset\:\Longleftrightarrow\:M\text{ accepts }w\end{cases}$$ So we can easily define: $$S(\langle M,w\rangle)=\begin{cases}\text{accept}\:\Longleftrightarrow\:M_E(\langle M_1\rangle)\text{ reject}\\\text{reject}\:\Longleftrightarrow\:M_E(\langle M_1\rangle)\text{ accept}\end{cases}$$

And note that this is, by definition, a decider for $A_{TM}$, because it accepts if and only if $M$ accepts $w$, and it rejects if and only if $M$ does not accept (i.e. rejects or runs on the input indefinitely) $w$.

Answer 2

You shouldn't focus on what is happening in step 1.2, you should think at it just as part of a definition for $M_1$. In fact, the supposition that $M_E$ decides $E_{TM}$ grants that if $M_E(<M_1>)$ accepted it means that $M(w)$ accepted too. Keep in mind that $<M_1> \in E_{TM} \iff M_E(<M_1>) accepts \iff M(w) accepts \iff <M,w> \in A_{TM}$, which is the meaning of the reduction itself: you are deciding wether $<M,w> \in A_{TM}$ by using the decider $E_M$, but you know that $A_{TM}$ is not decidable so that's a contradiction.