# Reduce ATM to CFTM

How would I reduce $A_{TM}$ to $CF_{TM}$ when: $A_{TM}=\{<M,w>|M$ is a Turing Machine description and $w\in L(M)\}$

$CF_{TM} =\{<M> | M$ is a Turing Machine description $L(M)$ is a context-free language.$\}$

My problem is this: $A_{TM}$ deals with all $TM$s how would knowing if some $TM$'s language is $CF$ help us know if $w \in L(M)$ ?

• Take a look at this post, and try to modify the proof to CFL. – Shaull Mar 20 '18 at 16:20

If I read you correctly, you have the reduction wrong. Essentially, you need to use a transformation $f$ from an instance of $A_{TM}$ to an instance of $CF_{TM}$ such that $$\langle{M, w}\rangle\in A_{TM} \Longleftrightarrow L(f(\langle{M, w}\rangle)) \text{ is a CFL}$$ To this end, let's define $f(\langle{M, w}\rangle)$ to be the description of a TM $N$ where

N(x) =
if x = a^(2^n) for some n
return accept
else if M(w) = accept and x = a^k for some k
return accept


Now if $\langle{M, w}\rangle\in A_{TM}$, it's clear that $L(N)=a^*$, the language of all strings of as which, being regular, is certainly a CFL. On the other hand, if $\langle{M, w}\rangle\notin A_{TM}$ then we skip the else part of the code of $N$ and so $$L(N) = \{a^{2^n}\mid n\ge 0\}$$ which is well-known to be not a CFL.

This, by the way is a very handy idiom: have both parts accept a non-"whatever" language and the last part activate to add enough strings to get what you need to make a "whatever" language.

• else if M(w) = accept and |x| = a^k for some k...you mean else if M(w) = accept and x = a^k for some k ? – Anwar Saiah Mar 21 '18 at 5:45
• It is also not so clear for me, why L(N) is CFL or REGULAR when you say "if M(w) = accept and x = a^k for some k"..you have to define what x is for that matter cause there's no such input. Our input is just <M,w>. – Anwar Saiah Mar 21 '18 at 5:51
• Other than that your solution is very convincing, but needs to be more clarified, Thanks. – Anwar Saiah Mar 21 '18 at 5:53
• @AnwarSaiah. First, thanks for the catch about $|x|$, it's now fixed. For your second comment, if $M$ accepts $w$, then $N$ will accept any string of $a$s and only those, so $L(N)$ in that case is $a*$ – Rick Decker Mar 21 '18 at 16:18