1
$\begingroup$

I could not think of a way to concisely write down my question clearly, but I'd like to ask, from Sipser's book, $ALLCFG$ is an undecidable language (where $ALLCFG$ means that $G$ is a $CFG$ that generates $\sum ^*$).

In his textbook, there is a polynomial reduction from $\bar{{ATM}}$ (complement of $ATM$, where $ATM$ is the language that a $TM$ accepts input string $w$) to $ALLCFG$, where the reduction works by mapping $\sum ^*$ to all non-accepting configurations, i.e. if there is an accepting configuration from $G$, then $G$ does not generate $\sum ^*$.

But Sipser does not seem to clarify if $ALLCFG$ is also not turing-recognizable. Since $\bar{ATM}$ (a non computably enumerable language) polynomially reduces to $ALLCFG$, does this mean that $ALLCFG$ is also not computably enumerable? i.e. not turing-recognizable.

Which brings me to my main quesiton -- if $ALLCFG$ is indeed not-turing recognizable, then its complement should be turing recognizable since it would in turn reduce to $ATM$ -- but how should this language be phrased?

P.S. It could not be whether a $CFG$ generates a string $s$ since this language is decidable, but $ATM$ is turing-recognizable only and not decidable

$\endgroup$
  • $\begingroup$ ALLCFG is not recognizable - by reduction from $\overline{ATM}$ - but its complement is recognizable, using the algorithm deciding whether a word belongs to the language of a CFG. $\endgroup$ – Yuval Filmus Dec 2 '18 at 8:07
  • $\begingroup$ Thanks , although deciding whether a word belongs to a CFG should be a decidable problem right?... But if it is decidable then its complement should be turing recognizable which in this case isn't... $\endgroup$ – Link L Dec 2 '18 at 9:07
  • $\begingroup$ These are not the same problems - there’s a step missing here. $\endgroup$ – Yuval Filmus Dec 2 '18 at 17:14

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.