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 ∑∗).
In his textbook, there is a polynomial reduction from ¯ATM (complement of ATM, where ATM is the language that a TM accepts input string w) to ALLCFG, where the reduction works by mapping ∑∗ to all non-accepting configurations, i.e. if there is an accepting configuration from G, then G does not generate ∑∗.
But Sipser does not seem to clarify if ALLCFG is also not turing-recognizable. Since ¯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
Answer
Attribution
Source : Link , Question Author : Link L , Answer Author : Community