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

Question

First definition:

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

Second definition:

$E_{TM} = \{ <M> |$ 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 $<M>$, 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."

2. Ask the oracle: Is $<N, 0> \in A_{TM}$.
3. 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.

Answer 1

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.}