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

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.

• You write about a $L(F((\langle M, w \rangle)))$. What is this supposed to mean? Apr 8, 2019 at 9:23
• that if x exists in $A_{TM}$ then there should be a x in f(x) to make the reduction, when f(x) is CF. so i need to take language as a function of A_TM and make it an instance of $CF_{TM}$. i think i should've chosen the function to be for $a^2^n$ format, because if $A_{TM}$ accepts it then a* is regular and also a CFL, and if it doesn't accept then it is not a cfl. but my main problem is why the compliment. could you please help me with that? Apr 8, 2019 at 9:40

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.