We still haven't explicitly linked the notion of computation as we understand it today with the Turing machines that we have been studying so far. All of the problems we've studied until now appear to be formal language problems. That is, we've been constructing Turing machines in order to decide various languages. However, we can look at these languages from the computational point of view. For instance, we can consider a Turing machine that decides the language $L_{pal}$ to be an algorithm for determining whether a given word is a palindrome.
In fact, it turns out we can view many computational problems as language inclusion problems. We say that a problem that results in an answer of yes or no is a decision problem. A decision problem $P$ has an associated language $L_P$. Then an input $w$ corresponds to a yes for problem $P$ if and only if $w \in L_P$.
Implicit in the correspondence between problems and languages is the assumption that all of our inputs are strings. We can always encode objects into string form. Suppose we have an object $O$. Then the string representation or encoding of $O$ is denoted by $\langle O \rangle$. If we have several objects $O_1, O_2, \dots, O_k$, then we denote their encoding into a single string by $\langle O_1, O_2, \dots O_k \rangle$. We assume that our objects can be encoded into a reasonable encoding which a Turing machine can decode.
Suppose we wanted to know whether a given undirected graph is connected. An undirected graph is connected if every node can be reached from every other node. In other words, we want a Turing machine that decides the language $$ L = \{ \langle G \rangle \mid \text{$G$ is a connected undirected graph} \}. $$
Now, we need to consider a proper encoding for graphs. Recall that a graph is a pair $G = (V,E)$, where $V$ is a set of nodes or vertices and $E$ is a set of edges, which are pairs of vertices. Then we can encode a graph $G = (V,E)$ by as follows: $$ \langle G \rangle = (v_1,v_2,\dots,v_n)((v_{e_1,1},v_{e_1,2}),(v_{e_2,1},v_{e_2,2}),\dots,(v_{e_m,1},v_{e_m,2})). $$ where $v_i \in V$ are vertices. This particular encoding is a list of all of the vertices in the graph followed by a list of all of the edges. Now, it is not too difficult to see how a Turing machine can decide $L$.
We'll be looking at examples of decidable languages and how to describe Turing machines that decide them. In particular, we'll be drawing from problems in formal language theory and revisiting some properties of regular and context-free languages. While we'll see that a lot of problems are decidable, formal language theory has some very stark examples of problems which are unsolvable. We begin with regular languages, many decidability properties of which were shown by Rabin and Scott in 1959.
The simplest problem we can ask about a DFA and a word is whether the DFA will accept the word. This problem is obviously decidable. We define the following language for the DFA acceptance problem: $$ A_{DFA} = \{\langle B, w \rangle \mid \text{$B$ is a DFA that accepts $w$}\}.$$
Theorem. $A_{DFA}$ is a decidable language.
The idea of the proof is rather simple: we simply simulate $B$ on the input string $w$. How does would a Turing machine do this? The machine would need to keep track of two things:
Then the machine accepts the input if and only if $B$ is in an accepting state when the last symbol of $w$ is processed. Otherwise, it rejects.
We can ask the same question for NFAs: $$ A_{NFA} = \{\langle B, w \rangle \mid \text{$B$ is an NFA that accepts $w$}\}.$$
Theorem. $A_{NFA}$ is a decidable language.
Here, we can take advantage of the theorem we just proved above. We can construct a Turing machine that does the following on the input $\langle B,w \rangle$, where $B$ is an NFA and $w$ is an input word:
This machine demonstrates two ideas. The first is that we can use other Turing machines as subroutines like a typical programmer would think of doing. The second is that we are able to convert NFAs to DFAs, so we don't need to consider DFAs and NFAs separately anymore.
Now, we want to determine whether a given DFA will accept any strings. We will consider the following language $$ E_{DFA} = \{ \langle A \rangle \mid \text{$A$ is a DFA and $L(A) = \emptyset$}\}. $$
Theorem. $E_{DFA}$ is a decidable language.
To solve this problem, we simply treat it like a graph problem. A DFA accepts a word if there is an accepting state that is reachable from the initial state. Then we can use a similar idea to the graph connectedness algorithm from last week for this problem. The TM looks like this:
Another major property of regular languages that is of use is to figure out whether one language is contained in another. This is expressed via the following language, $$ CO_{DFA} = \{ \langle A,B \rangle \mid \text{$A$ and $B$ are DFAs and $L(A) \subseteq L(B)$} \}.$$ Of course, this is another decidable property, so we have the following theorem.
Theorem. $CO_{DFA}$ is a decidable language.
Again, we make use of the machine that we constructed in the previous theorem. First, let's consider what it means for $L(A)$ to be contained in $L(B)$. We want to check whether every word in $L(A)$ is also in $L(B)$. However, an equivalent way of checking this property is to check whether there are any words in $L(A)$ that are not in $L(B)$. So we construct a DFA $C$ such that $$ L(C) = L(A) \cap \overline{L(B)}$$ and check whether or not $L(C) = \emptyset$. Luckily, we've just shown how to check the emptiness of a DFA.
The last major formal languages question we'll cover in class deals with equality. Given two DFAs $A$ and $B$, do they recognize the same language? We have the following language, $$ EQ_{DFA} = \{ \langle A,B \rangle \mid \text{$A$ and $B$ are DFAs and $L(A) = L(B)$} \}.$$
Theorem. $EQ_{DFA}$ is a decidable language.
Of course, we have the opportunity to make use of the machine that we constructed in the previous theorem. Recall that for two sets $S$ and $T$, $S = T$ if and only if $S \subseteq T$ and $T \subseteq S$. This fact combined with the containment machine we constructed gives us a rather simple algorithm for checking equality.
There is one more important property: universality. This is the problem of determining whether or not a given DFA accepts every string. In other words, does $L(A) = \Sigma^*$? Again, this is fairly straightforward based on the results we've already shown. One approach is to construct a simple DFA that recognizes $\Sigma^*$ and test whether $\Sigma^* \subseteq L(A)$. Another approach is the check whether $\overline{L(A)} = \emptyset$.
Now, we'll turn our attention to the class of context-free languages. Recall that context-free languages are recognized by pushdown automata and are generated by context-free grammars, but we're going to be dealing mainly with context-free grammars. As you might expect, things will get a bit more complicated, especially as grammars are fairly different objects from finite automata and we don't have many of the same nice properties of regular languages to rely on. Many of these results originate from the same paper that investigated closure properties of CFGs that was mentioned earlier by Bar-Hillel, Perles, and Shamir in 1961.
Again, we begin with membership. In the case of a grammar, rather than acceptance, we have the problem of whether a grammar generates a particular string. Thus, we have the following language $$ A_{CFG} = \{\langle G, w \rangle \mid \text{$G$ is a CFG that generates $w$}\}.$$
Theorem. $A_{CFG}$ is a decidable language.
Since we're trying to determine generation rather than acceptance, the algorithm is not as straightforward as in the case for DFAs. The obvious solution of just trying every single possible derivation doesn't quite work, since there are infinitely many derivations that we have to try. If $w$ wasn't generated by $G$, then the algorithm would never halt and our language wouldn't be decidable.
To solve this, we need to take advantage of a property of context-free grammars. Remember that we can transform any grammar into an equivalent grammar in Chomsky normal form and that any derivation of a word of length $n$ has exactly $2n-1$ steps. Therefore, instead of checking every derivation, we only need to check derivations with $2n-1$ steps, of which there are only finitely many. Then the Turing machine operates as follows:
We can also show that the emptiness problem for CFGs is also decidable. Again, it'll look a bit different from what we've done with DFAs. First, here's the language $$E_{CFG} = \{\langle G \rangle \mid \text{$G$ is a CFG and $L(G) = \emptyset$} \}.$$
Theorem. $E_{CFG}$ is a decidable language.
In a way, we can apply the same kind of idea from the DFA case. Of course, a grammar isn't a graph, so it's not exactly the same. However, in essence, what we want to do is check that there's a derivation that will generate some terminal beginning from the start variable. To do this, we check each variable to see if it can generate a string of terminals. We begin by marking terminals and determining whether each variable can generate a string of variables and terminals that are all marked. Once the algorithm is finished, we can simply check whether the start variable is marked or not.
Now we'll consider the problem of determining whether two grammars generate the same language. This is the language $$ EQ_{CFG} = \{\langle G,H \rangle \mid \text{$G$ and $H$ are CFGs and $L(G) = L(H)$}\}.$$ This turns out to be challenging. Unlike regular languages, we can't rely on intersection and complementation, since context-free languages aren't closed under these operations. However, even if we tried harder, we won't be able to solve this problem, as it turns out to be our first encounter with an unsolvable problem. Furthermore, the undecidability of equality for CFLs implies the undecidability of the containment and universality problems.