# Issues in the proof of $E_{TM}$ is Turing reducible to $A_{TM}$

First definition:

$$A_{TM}$$ = $$\{ |$$M is a TM and M on w accepts$$\}$$

Second definition:

$$E_{TM} = \{ |$$ M is a TM and L(M) = $$\phi \}$$

Let $$T^{A_{TM}}$$ be an oracle Turing machine with an oracle $$A_{TM}$$. We want to show that $$E_{TM}$$ is Turing reducible to $$A_{TM}$$.

$$T^{A_{TM}}$$ = "On input $$$$, where M is a TM:

1. Construct a TM N:
1. N = "On any input:
2. For i=0, 1, 2, 3. Run M on s_i for i steps where $$s_i \in \Sigma^*$$ and $$\Sigma^*=\{s_0, s_1, s_2, .... \}$$.
3. If M accepts any of these strings, then accept."
1. Ask the oracle: Is $$ \in A_{TM}$$.
2. If the oracle answers NO, accept. If YES, reject."

Now, Sipser said in pp. 236-237, "If M's language isn't empty, N will accept every input and in particular, input 0. Hence the oracle will answer YES, and $$T^{A_{TM}}$$ will reject. Conversely, if M's language is empty, $$T^{A_{TM}}$$ will accept."

My question: Why N will accept every input and in particular, input 0? It is not clear how N will accept every string. For example, M will run on all input of $$\Sigma^*$$ but only those strings that are in L(M) will be accepted and I don't understand how N will accept every input. Moreover, it is not clear why he choose string "0".

Note that I changed step 2 where Sipser wrote: "Run M in parallel on all strings in $$\Sigma^*$$" since as I believe mean the same thing unless you have something to say.

First, note that Sipser says ""If M's language isn't empty, N will accept every input".

Let us first prove this statement: Assume $$L(M) \neq \emptyset$$.

Then there exists some $$x \in L(M)$$. Because $$L(M) \subseteq \Sigma^*$$ we have $$x \in \Sigma^*$$. Then because $$s_i \in \Sigma^*$$ and $$\Sigma^*=\{s_0, s_1, s_2, .... \}$$, there exists an $$i^*$$ such that $$s_{i^*} = x$$.

The TM $$N$$ accepts "if M accepts any of these strings". Because $$s_{i^*}$$ is one of these strings, $$N$$ accepts.

Note that $$N$$ never considered its own input! It only decides whether to accept or not based on $$M$$ which is part of the TM $$N$$ itself, not $$N$$'s input.

The string 0 is totally arbitrary. You can pick any string because we know that $$N$$ will accept any string if and only if* the language of $$M$$ is not empty. Because we want to reduce to $$T^{A_{TM}}$$ this is indeed all we care for.

* The other direction remains to be shown for a complete proof.

• Thank you Idmean, so If M's language isn't empty, it does accept only those strings that are membership of L(M) but not all strings of $\Sigma^*$ (since in Sipser's words that says N will accept every input means to me that L(M) = $\Sigma^*$). Jul 7 at 13:34
• Now, you said that N accepts if M accepts any of these strings (the strings that are in L(M) but not all strings in $\Sigma^*$). Now, how this would imply "N will accept any string iff language of M is not empty"? Jul 7 at 13:40
• Maybe his phrasing is confusing, but Sipser certainly didn't mean to imply $L(M) = \Sigma^*$. Concerning "N will accept any string iff language of M is not empty": I proved the forward direction in the answer. Is there something unclear about the proof itself? Or are you asking about the other direction? Jul 7 at 13:48
• Another hint that may clear up some confusion: Consider again that $N$ never uses its input in any way. It doesn't even need to read it. Jul 7 at 13:50
• Yes, I have a question. For example, why we choose string 0? Suppose M is a TM that decides all strings that are starting with 1. Now L(M) = {1, 10, 11, 100, ...}. Now If we plug this M into $T^{A_{TM}}$, then $T^{A_{TM}}$ in step 2 will say No, since N on input 0 doesn't accept (reject/loop). This imply that the oracle will return NO. Therefore, $T^{A_{TM}}$ accepts. This means that M's language is empty. Now can you tell me what went wrong? Jul 7 at 13:58