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

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

• You should probably define $E_{TM}$ and $A_{TM}$ in order to make the question self-contained. Commented May 19, 2022 at 10:58
• My choice would have been the straightforward proof by diagonalization that shows $E_{TM}$ is not computably enumerable had there been a poll for "the standard proof for the undecidability of $E_{TM}$" Commented May 20, 2022 at 1:47

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.

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

• Hi, I edited the question to make it clearer. Commented May 19, 2022 at 12:15
• This answer was given before you added the definition of $A_{TM}$ and is using the different definition $A_{TM} = \{ \langle T \rangle \mid L(T) = \Sigma^* \}$. Commented May 19, 2022 at 12:53