Lately I need to find the decidability of the following decision problem:
If $L$ is a context-free language, is $\overline{L}$ also context-free?
I know that context-free language is not closed under complementation. Had it been otherwise, this decision problem would have been trivially decidable, since a Turing machine that always answer "YES" can decide the problem.
Few of my peers say that the problem is undecidable since CFLs are not closed under complementation. This logic/reasoning seems utter nonsense to me.
Yet few other peers try arguing about the decidability of the problem using Rice Theorem as follows:
Let $L$ be set of all CFLs. For this language whether any member's complement is CFL or not is a nontrivial property, since CFL are not closed under complementation. So According to Rice theorem it is undecidable.
Is the argument above correct in the first place? The Rice Theorem states that :
Any nontrivial property of Recursively Enumerable Languages is undecidable.
And my peers probably justifies this argument about Rice Theorem saying that all CFLs are also RE languages. But as I understand, the "property" in Rice Theorem is a predicate where the universe of discourse is the set of RE languages. If they reduce/chop this universe of discourse to contain only CFLs, would things remain the same? I do not think so, [I might be wrong however.] in the sense that we are dealing with just a small fraction of the entire set. For instance, the set $\mathbb{N}$ is closed under addition, but the set $\{1,2,...,10\}$ is not.
To apply Rice Theorem, I would define the language of the property as:
$$L_p=\{\langle M \rangle \mid L(M)\text{ is a context-free language and }\overline{L(M)}\text{ is a context-free language}\}$$
The language $L_p$ is undecidable, because the property that "a RE language is context-free and its complement is context-free", is non-trivial. But this non-triviality arises primarily due to the check of a RE language being context-free. Is the actual decision problem correctly addressed by the $L_p$ above?
Moreover for decidability question I usually try to design a TM machine, but I have no clue to this decision problem. Given a CFL (using a finite description of course), how do I design the TM to find the complement of this finite description? Once this complementation is done, we should check whether the language produced is a CFL. But how? I cannot proceed further.
Or is this decision problem much more notorious than it seems? How can we approach the problem beyond what I have written?
PS: The beautiful answer to a similar question answers the decidability question, but it remains mysterious to me whether the approach of my peers using Rice-Theorem is at all correct, and what could have been a raw TM machine approach? This is how my question slightly differs from this question.