Prove that "If $L$ is a context-free language, is $\overline{L}$ also context-free?" is undecidable

Question

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.

Answer 1

Rice's theorem can't help.

You are right that Rice's theorem isn't applicable, and you're right about the reason.

You've been given a decision problem about (context-free) languages. Meaning, you're trying to design a Turing machine that takes in a context-free language as input (for example, your machine might accept only valid context-free grammars as input). And it is supposed to output YES or NO based on whether the complement of that language is also context-free.

Rice's theorem applies exclusively to decision problems about turing machines. Meaning, a situation where you're trying to design a Turing machine that takes in a Turing machine as input and answers YES or NO based on whether the input machine's language has a particular property.

It is true that, according to Rice's theorem, the property: "M is a turing machine whose language is context free and where the complementary language is also context-free" is undecidable. But this fact is, unfortunately, useless because it tells you that a property of machines is undecidable. You want to know whether a property of context-free languages is undecidable. Rice's theorem can't help you.

How do you design a decider?

If the language "<G> : G is a context-free language whose complement is also context free" is decidable, then there's some algorithm for deciding it, even if it takes some thought. But, if the language is undecidable, then there's no algorithm for deciding it. So you have two approaches:

1. If you think the problem is decidable, you can try to develop an algorithm—design a TM, for example. Or:
2. If you think the problem is undecidable, try to think of the different proof strategies you have for showing that a problem is undecidable.

You can switch back and forth between these approaches, of course. If the language is undecidable, then you won't be able to come up with an algorithm (!). If the language is decidable, then you won't be able to come up with an undecidability proof (!).

Proof of undecidability

The usual tool for proving undecidability is a reduction from another hard problem. You show that if you did have an algorithm for deciding your problem, you could use it as a subroutine to solve another problem you already know is undecidable. This is a proof by contradiction.

The proof you reference is a good example.