Why is $A_{TM}$ not mapping reducible to $E_{TM}$?

Question

$A_{TM}= \{ \langle M,w\rangle \mid M$ is a TM that accepts $w\}$

$E_{TM}= \{ \langle M\rangle \mid L(M) = \emptyset \}$

The standard proof for the undecidability of $E_{TM}$ is given in this question, right?. Doesn't this automatically create a mapping reduction $f$ from $A_{TM}$ to $E_{TM}$ ? Whenever $w \in A_{TM}, f(w) \in E_{TM} $ obviously. The other way: $ f(w) \in E_{TM} \Rightarrow w \in A_{TM} $ seems true, although I suspect that's where the fundamental restriction lies. Can someone clarify this?

The proof given for $A_{TM}$ not being Turing reducible to $E_{TM}$ is the following:

Suppose for a contradiction that $A_{TM}$ $≤_{m}$ $E_{TM}$ via reduction $f$. This means that $w ∈ A_{TM} \iff f(w) ∈ E_{TM} $, which is equivalent to saying $w \notin A_{TM} \iff f(w) \notin E_{TM} $. Therefore, using the same reduction function $f$, we have that $\overline{A_{TM}} \le_m \overline{E_{TM}} $. However, $\overline{E_{TM}}$ is Turing-recognizable and $\overline{A_{TM}}$ is not Turing-recognizable.

I understand the proof above I think. It seems I am misunderstanding something fundamental about mapping reductions, or that I am confused about some step in the reduction from $A_{TM}$ to $E_{TM}$ in the standard proof.

Answer 1

Given $\langle M,w\rangle\in A_{TM}$, the mapping $f$ in the question maps $\langle M,w\rangle$ to $\langle M_1\rangle$, where Turing machine $M_1$ accepts input $x$ iff $x$ is $w$ and $M$ accepts $w$.

$f$ is NOT a mapping reduction from $A_{TM}$ to $E_{TM}$, since $M_1$ accepts $w$, i.e., $f(\langle M,w\rangle )=\langle M_1\rangle\not\in E_{TM}$ when $\langle M,w\rangle \in A_{TM}$.

On the other hand, $f$ is a mapping reduction from $A_{TM}$ to $\overline{E_{TM}}$, if we let $f$ map any string not of the form $\langle M,w\rangle$ to $\langle M_{\text{loop}}\rangle$, where $M_{\text{loop}}$ is a Turing machine that runs forever for all inputs.

---

The reason why $A_{TM}$ is not mapping reducible to $E_{TM}$ is given by the proof in the question.

Answer 2

Note: This answer was given before the definition of $A_{TM}$ was added to the question and was assuming the following definition instead $A_{TM} = \{ \langle T \rangle \mid L(T) = \Sigma^* \}$.

$E_{TM}$ is mapping reducible to $A_{TM}$. Here is a sketch of a possible reduction:

Given (the description of) a Turing Machine $T$, compute (the description of) a Turing Machine $T'$ that behaves as follows:

• $T'$ takes two inputs, a word $w$ and a non-negative integer $n$.
• $T'$ simulates $T$ with input $w$ for $n$ steps.
• If the simulation of $T$ accepts within $n$ steps, $T'$ rejects.
• Otherwise, $T'$ accepts.

If $T \in E_{TM}$ then for every word $w$ and every integer $n$, the simulation of $T(w)$ either rejects or does not halt within $n$ steps, causing $T'$ to accept. Therefore $T' \in A_{TM}$.

If $T \not\in E_{TM}$, then there is some word $w$ for which $T(w)$ accepts. Let $n$ be the number of steps taken by $T(w)$ to accept. The Turing Machine $T'$ with inputs $w$ and $n$ rejects. Therefore $T \not\in A_{TM}$.