There is a similar result characterizing undecidable properties of languages for subclasses of decidable languages (i.e. context-free languages, context-sensitive languages, etc.) called Greibach's theorem, due to Sheila Greibach in 1963 (you may remember Greibach being mentioned when were talking about normal forms for grammars).
We won't prove Greibach's theorem, but we will show that some problems about context-free languages are undecidable. The proofs for these kinds of problems are going to be much trickier, since we don't have the benefit of conjuring up Turing machines. However, we can do something that may be surprising, which is make use of computations of Turing machines.
Let $M$ be a Turing machine and $w$ and input string. An accepting computation path for $M$ on $w$ is a sequence of configurations $C_1, \dots, C_\ell$, where $C_1$ is the start configuration of $M$ on $w$ and $C_\ell$ is an accepting configuration of $M$ on $w$ and each $C_i$ follows directly from $C_{i-1}$ (that is, $C_{i-1} \vdash C_i$) as defined by the transition function of $M$. (We can define a rejecting computation path similarly.)
This gives us a very strict format for the computation of a word $w$ when run on a Turing machine $M$. We can consider the language of encodings of all such computation paths. For a fixed Turing machine $M$ and input string $w$ that we would like to run on $M$, we have the language of accepting configurations \[A(M,w) = \{\llbracket C \rrbracket \mid \text{$C$ is an accepting computation path for $M$ on $w$}\}.\] What does such a string look like? It must satisfy the following conditions:
Notice that our encoding of the computation path reverses every other configuration. This is a deliberate choice—we will get to it shortly. However, for each of the items in the previous list, we can define a language $A_i$ for them. Then the language of valid encodings of computation paths can be expressed as the intersection $$A(M,w) = A_1 \cap A_2 \cap A_3 \cap A_4,$$ which is all strings which satisfy all of our conditions.
At this point, the approach seems straightforward: if $M$ accepts $w$, then the language $A(M,w)$ should not be empty. We saw that we can do this if $A(M,w)$ is context-free. Unfortunately, this is not true: the set of strings described by Condition 4 is not actually context-free.
However, we can take a more indirect route: we'll show instead that the strings that don't satisfy all of these conditions—the strings that aren't valid accepting computation paths for $M$ on $w$—are a context-free language.
The language $\overline{A(M,w)}$ is a context-free language.
We note the language of valid encodings of computation paths expressed as the intersection $$A(M,w) = A_1 \cap A_2 \cap A_3 \cap A_4,$$ where $A_i$ is the language of strings that satisfy condition (i) above. Then by De Morgan's laws, we have $$\overline{A(M,w)} = \overline{A_1} \cup \overline{A_2} \cup \overline{A_3} \cup \overline{A_4}.$$ Then, we must show that each $\overline{A_i}$ are context-free languages. The first three are easy: $A_1, A_2, A_3$ are actually regular. Let $\Sigma = \Gamma \cup Q \cup \{\#\}$.
It's not hard to see that we can come up with regular expressions for each of these languages. Once we have that, then we get that their complements are also regular and therefore they are context-free.
The not so obvious part is showing that $\overline{A_4}$ is context-free. Many strings that are obviously not valid accepting computation paths are going to be in this language. The main case we have to watch out for is when we have a string that is very close to being or almost a valid computation path.
Suppose that we have such a string that is "almost" correct—in other words, it satisfies conditions 1 through 3. To fail condition 4, we must find a substring $\#C_i\#C_{i+1}^R\#$ such that $C_i \not\vdash C_{i+1}$. Suppose we are using a PDA to do this. When reading $C_i$, we push every symbol of $C_i$ onto the stack. Then when reading $C_{i+1}^R$, we pop every symbol of the stack to compare.
What do we look for? The crucial thing to notice here is that the change to the configuration by following a single transition of a Turing machine is very localized around the position of the tape head. This means that most of the configuration is going to be the same and we can simply make sure the symbols we see are the same.
However, we need to be careful around the location of the tape head. There are two possibilities:
Notice that we can have a difference that is valid around the tape head, since this indicates that a new symbol was written and the tape head has moved. But since the tape head can only move left or right one cell, we know that the tape head can only be at most two cells away from any difference. So when comparing configurations, we simply need to check that every substring of length 3 is valid—either it's the same or it is a valid change according to the transition function.
Since our language is specific to $M$, we can compare the two configurations against the transition function of $M$ and there are only finitely many possible changes that one can make.
Then since each of $\overline{A_i}$ are context-free, their union, $\overline{A(M,w)}$, is also context-free.
Why does this help? Recall that our original approach was to ask whether there were any valid accepting computation paths—whether $A(M,w)$ was non-empty. But since we know $\overline{A(M,w)}$ is context-free, we ask the opposite: Is $\overline{A(M,w)}$ every string? If it is, then $A(M,w)$ is going to be empty.
But if we can answer this question, then we can determine whether $M$ accepts $w$. But this is exactly the universality problem for context-free languages: $$U_{\mathsf{CFG}} = \{\llbracket G \rrbracket \mid \text{$G$ is a CFG and $L(G) = \Sigma^*$} \}$$
So undecidability follows immediately.
$U_{\mathsf{CFG}}$ is undecidable.
We will assume that $U_{\mathsf{CFG}}$ is decidable and show that doing so will allow us to decide $A_{\mathsf{TM}}$. Consider the language $\overline{A(M,w)}$ of strings that are not accepting computation paths for $M$ when run on $w$. Observe that $M$ accepts $w$ if and only if there is an accepting computation path $C$ for $M$ when run on $w$. So $C \in A(M,w)$ and therefore $C \not \in \overline{A(M,w)}$. Then $A(M,w) = \emptyset$ if and only if $M$ does not accept $w$, or equivalently, $M$ does not accept $w$ if and only if $\overline{A(M,w)} = \Sigma^*$.
Now, suppose we have a Turing machine, say $T$ that decides $U_{\mathsf{CFG}}$. Then we can construct a Turing machine $S$ that decides $A_{\mathsf{TM}}$ that does the following:
Since $A_{\mathsf{TM}}$ is undecidable, we can conclude that $U_{\mathsf{CFG}}$ is undecidable.
We can then use this to show that containment for CFGs is undecidable.
$C_{\mathsf{CFG}}$ is undecidable.
Suppose $C_{\mathsf{CFG}}$ is decidable and let $T$ be the Turing machine that decides it. We will define a TM $S$ that will decide $U_{\mathsf{CFG}}$ that does the following:
Our TM $S$ will accept if and only if $L(G') \subseteq L(G)$. But $L(G') = \Sigma^*$, so our TM accepts if and only if $\Sigma^* \subseteq L(G)$. Since $L(G) \subseteq \Sigma^*$, $S$ accepts $\llbracket G \rrbracket$ if and only if $L(G) = \Sigma^*$. But $U_{\mathsf{CFG}}$ is undecidable, so this is a contradiction and therefore $C_{\mathsf{CFG}}$ is not decidable.
We can use almost the same proof to show that $\mathsf{EQ}_{\mathsf{CFG}}$ is undecidable.
$\mathsf{EQ}_{\mathsf{CFG}}$ is undecidable.
This technique of defining CFLs to generate Turing machine computations (or not Turing machine computations, as it turns out) was shown by Hartmanis in 1967. He shows that several other decision problems regarding CFGs are undecidable using the same approach.
The situation for CFLs is a bit surprising—they seem to be far less powerful than even decidable languages, but are complex enough to encode behaviours of these more powerful devices. As a result, a surprising number of problems about CFLs are undecidable. In fact, it's not until we descend all the way down to a class of (non-regular) languages called the visibly pushdown languages, a subclass of deterministic context-free languages, that we get decidability for all of our decision problems again.
| Class | Membership | Emptiness | Inclusion | Equivalence | Universality |
|---|---|---|---|---|---|
| Regular | Decidable | Decidable | Decidable | Decidable | Decidable |
| Visibly pushdown | Decidable | Decidable | Decidable | Decidable | Decidable |
| Deterministic context-free | Decidable | Decidable | Undecidable | Decidable | Decidable |
| Linear | Decidable | Decidable | Undecidable | Undecidable | Undecidable |
| Context-free | Decidable | Decidable | Undecidable | Undecidable | Undecidable |
You can ignore this—this isn't going to be on the final exam.
To cap things off, let's go back to where computer science started, branching off from mathematical logic. Recall that the genesis of all of this stuff was rooted in the problem of trying to formalize mathematics. The idea was that a sentence in first-order logic could be proven by syntactic manipulation—string rewriting via inference rules.
Kurt Gödel proved the Completeness Theorem in 1930—that if you had a set of consistent first-order sentences $\varphi$, you could come up with a proof for them. This is a purely syntactic result. The problem comes when we want to know what the sentences mean—the proof proceeds by showing that we can always "reverse-engineer" a valid theory for our set of consistent sentences.
This is not helpful if we have a specific theory in mind, like Peano arithmetic or Zermelo–Fraenkel set theory. So the task then is to show that this works for a particular theory: if we start with a bunch of axioms, we would be able to mechanically prove theorems. What would such a system look like? We would want the following properties for our system.
In 1931, Gödel follows up his Completeness Theorem with the Incompleteness Theorems. The First Incompleteness Theorem states that any sufficiently powerful consistent and computable theory $\mathcal T$ is incomplete—there exists a sentence $\varphi$ for which $\varphi$ or $\neg \varphi$ do not have a proof in $\mathcal T$.
Said more informally, this means there are statements that we can make for which a proof doesn't exist. This is obviously pretty significant if your goal is to be able to mechanically prove every statement that is expressible. You might expect that the original proof is pretty complicated, and it is. However, we can use what we've been doing over the last few classes to come up with a relatively short but convincing proof—as long as you understand computation.
Choose your favourite theory $\mathcal T$ and assume it is complete. So for every statement $\varphi$, there is either a proof of $\varphi$ or a proof of $\neg \varphi$ in $\mathcal T$.
But if this assumption is true, then this will allow us to decide the Halting Problem. Here's how we can define the Turing machine $H$ to decide $\mathsf{HALT_{TM}}$:
Since $\mathcal T$ is complete, at least one of the two proofs must exist. This means that our search will eventually come across one of them and so $H$ is guaranteed to halt and give an answer, thus deciding the Halting Problem. But this is a contradiction since we saw earlier that $\mathsf{HALT_{TM}}$ is undecidable. So our assumption was false and $\mathcal T$ cannot be complete.
One important point we glossed over is that we need our theory $\mathcal T$ to be powerful enough to say something like "$M$ halts on $w$". This sounds very complicated, but Gödel's original proof was about how it's possible to say these sorts of things in Peano arithmetic. In other words, the theory of the natural numbers with addition and multiplication is quite powerful—enough to talk about computation, which is pretty surprising.
How does he pull it off? By doing kind of the same thing that Turing does by encoding Turing machines. Gödel defines what we now call Gödel numbering. This is just an encoding scheme for first-order sentences. In other words, he turns a string into a natural number. That's encoding!
Of course, he didn't talk about Turing machines—those would come a few years later, in 1936 due to Turing who himself was inspired by Gödel's work on the Incompleteness Theorems. But what Gödel does show is just as interesting. Again, we'll get right into it.
First, notice that other than completeness, we made an unstated assumption about $\mathcal T$—that it's consistent. What if we tossed that assumption? Inconsistency would give us the possibility that we do have proofs for halting or not halting, but not for what might actually occurs. For instance, we could find a proof that $M$ halts on $w$, even though $M$ doesn't halt. So generally, we would like our theories to be consistent.
Let's assume that $\mathcal T$ is consistent. We define our old friend, the Turing machine $D$ which does the following:
This Turing machine looks for proofs for whether a TM halts or not when it is run on its own encoding—a trick that we've seen a few times by now. And so we ask the same question that we've asked before: what happens when we run $D$ on $\llbracket D \rrbracket$? Again, two possibilities: it halts or it runs forever.
But this time, we can get an answer—we conclude that $D$ will run forever on $\llbracket D \rrbracket$. Why? Because these proofs can't exist!
Suppose they did. Then because we assumed that $\mathcal T$ is consistent, we'd end up in a contradiction as before. Otherwise, we could be in the situation where the proofs exist but $D$ does the "wrong" thing, contradicting consistency. So $D$ will keep searching through every string for these proofs, never finding them.
However, notice that our argument above is dangerously close to a proof that $D$ runs forever on $\llbracket D \rrbracket$: it is a proof that "$\mathcal T$ consistent $\rightarrow$ TM $D$ loops forever on $\llbracket D \rrbracket$". The missing piece, and what would push this over to be a proof that "$D$ loops forever on $\llbracket D \rrbracket$", is a proof for the statement "$\mathcal T$ is consistent".
This is how we get the Second Incompleteness theorem: the statement "$\mathcal T$ is consistent" is a statement in $\mathcal T$ that can't have a proof in $\mathcal T$.
Why? If we did have a proof that $\mathcal T$ was consistent, then we would immediately have a proof that $D$ loops forever on $\llbracket D \rrbracket$, from above. But the existence of such a proof causes us to enter the contradiction we just avoided.
Again, remember that Gödel was working with Peano arithmetic. So he was able to show that in Peano arithmetic, one can say "Peano arithmetic is consistent" and that this then can't have a proof in Peano arithmetic. This is both the existence of a sentence that is true without proof (the First Incompleteness Theorem) and is a statement about the consistency of the theory (the Second Incompleteness Theorem).
Like the results we've seen in computability, there are two takeaways, which funnily enough sound contradictory.
One final question we can consider is whether there are any theories that are decidable, consistent and complete. The answer is yes: Presburger arithmetic—the theory of the natural numbers with addition (but not multiplication). Büchi showed in 1960 that we can encode formulas of Presburger arithmetic as—surprise: ＼finite automata!／