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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.