Skip to main content
3 of 10
edited title

Why we can reduce $A_{TM}$ to $ALL_{CFG}$, but we can not reduce $A_{TM}$ to $E_{CFG}$

Like what we do with $ALL_{CFG}$, we can construct a $PDA$ that accepts the computation histories on $A_{TM} on string w, convert it to CFG, and use the decider of E_CFG to decide the problem.

If $A_{TM}$ can't accept string w, the computation history will not exist, thus $L(CFG)$ will be empty. If $A_{TM}$ can accept string w, the computation history will exist, thus $L(CFG)$ will not be empty.

My question is if we can decide whether L(CFG) is empty or not, based on the above construction, we can decide $A_{TM}$ already?