Finding a mapping reduction from $A_{TM}$ to $\overline{CF_{TM}}$

Question

I am trying to find a mapping reduction from $A_{TM}$ to $\overline{CF_{TM}}$, but I can't seem to find one.

Definitions: $$\begin{align*} CF_{TM} &= \left\{ \langle M \rangle \mid \text{$M$ is a TM and $L(M)$ is context-free} \right\} \\ A_{TM} &= \left\{ \langle M,w \rangle \mid \text{$M$ is a TM and $w \in L(M)$} \right\} \end{align*}$$

AFAIK the mapping reduction of the regular (i.e., not the complimentary) language is as follows: $\langle M,w \rangle \in A_{TM}$ if and only if we can construct a language $L$ which is context-free in the sense that $L(F((\langle M,w \rangle)))$ is context-free.

Answer 1

Let $L$ be recursively enumerable but not context-free (and, therefore, not empty). We only need the existence of such an $L$; the actual choice is immaterial. In addition, recall the empty set $\varnothing$ is context-free. The idea is to map to a TM which accepts $L$ in case $M$ accepts $w$ (i.e., $\langle M,w \rangle \in A_{TM}$) and to $\varnothing$ otherwise.

Given an instance $\langle M,w \rangle$ of $A_{TM}$, map it to the description $\langle S \rangle$, where $S$ is the TM which does the following:

On input $w'$:

1. Run $M$ on $w$. If $M$ rejects, reject.
2. If $M$ accepts $w$, then accept if and only if $w' \in L$.

Note that, if $M$ does not halt on $w$, then $S$ does not halt either. Also, $w' \in L$ can be checked because $L$ is recursively enumerable (and $S$ need not halt in case that is false). We conclude that $L(S) = L$ if $\langle M, w \rangle \in A_{TM}$ and $L(S) = \varnothing$ (which is context-free) otherwise.

---

An observation. The trick behind 98% of these problems lies in understanding what you need to do (i.e., what I wrote in the first paragraph). The actual description for the instance you are reducing to (in this case, $\langle S \rangle$) might look tricky or esoteric at first sight, but it actually simply follows as a consequence once you have the right ideas in mind.