This page is located at http://www.cs.bc.edu/~alvarez/Theory/decidability.html
For example, primality testing is equivalent to the problem of recognizing the language
We adopt this language viewpoint in order to address decidability in the framework of Turing machines, which have strings as inputs. As we saw in class, Turing machines are equivalent in computational power to programs written in a high-level language such as C++ or Java. In particular, a given computational problem is solvable by a computer program if and only if its language recognition version is solvable by a Turing machine. In the remainder of these notes I'll refer to the language versions of computational problems.
L is Turing enumerable if there is an enumerator Turing machine E that prints all strings in L and no other strings. The enumerator E does not have any inputs. When started, E starts printing strings on its output tape. E may stop after a while or it may continue printing forever. The time interval between consecutively printed strings may vary; E may have to compute for a while before being ready to print another string.
We proved the following result in class.
Theorem. A language is Turing recognizable if and only if it is Turing enumerable.
Theorem. The following language L is decidable.
In other words, the computational problem of determining whether a given DFA accepts an infinite language or not is decidable.
Proof: We must design a decider TM M that recognizes L.
First try an approach that's too good to be true. Let E be a Turing enumerator of the set of all strings over the On input w, D decodes w and determines whether w is the string encoding of a DFA M. If not, D rejects w. If w encodes a valid DFA M, D continues its computation by starting a Turing enumerator machine E for the set of all strings over the input alphabet of M. For each string s printed by E, D feeds s to M and waits for M to finish processing s. If M accepts s, D places s in a special "bin" containing all accepted strings. Once all strings printed by E have been processed in this way, D simply checks whether infinitely many of them have been placed in the bin. If so, D accepts w, declaring that the corresponding DFA M accepts an infinite language. If not, D rejects w. In any case, a decision is reached, so D is a decider.
Exercise. Explain why the above approach fails to yield a decider for L.
We need an alternate, more realistic, approach. First we show the following fact.
Lemma. If M is a DFA with p states, then M accepts infinitely many strings if and only if M accepts at least one pumpable string w of length less than 2p. The pumpability condition is that w may be split as a concatenation w=xyz with y nonempty such that all pumped strings x yn z (where n >=0) are also accepted by M.
Proof of the lemma: Clearly, if a pumpable string w as in the statement is accepted by M then M accepts infinitely many strings - namely all of the pumped versions of w. That proves the "if" direction of the if and only if statement. For the other direction, assume that M accepts infinitely many strings. We must show that M accepts a pumpable string w of length less than 2p, where p is the number of states of M. Since M accepts infinitely many strings, M must accept at least one string v of length p or greater (because there are only finitely many strings of length less than p over the finite input alphabet of M). Choose one such long accepted v. By the pumping lemma, this v is pumpable. We can't choose v as our w, though, because the length of v may be much larger than 2p. However, we'll show that we can extract a suitable w from v by arguing as in the proof of the pumping lemma. Split v as xyz as in the pumping lemma. Here, y is a nonempty substring of v that drives M in a loop from some state q of M to itself. The existence of such a y no later than the p-th symbol of v is guaranteed by the pigeonhole principle. The prefix substring x drives M from its start state to state q, and the suffix substring z drives M from q to an accepting state of M. We'll assume that we choose the leftmost possible y in v. As explained above, this y is guaranteed to be contained among the first p symbols of v. We know that the suffix z drives M from the loop state q to an accepting state qf. Repeating the pigeonhole argument on z, we see that some substring of z will drive M in a loop if z has length p or greater. In fact, if the length of z is p or more, then z can be split as z=rst, where s is nonempty and drives M in a loop. In this case, replace z by rt, that is, delete the middle s portion of z. If the length of the new z is still p or greater, iterate this process. Eventually, a string z' of length less than p will be reached that still drives M from the loop state q to the accepting state qf. Finally, let w be the string w = xyz'. By construction, w has length less than 2p, is accepted by M, and is pumpable. This completes the proof of the lemma.
Lemma. If M is a DFA and w is a string of length p or greater that is accepted by M, then there is a string w' of length strictly less than that of w that is also accepted by M.
With the first lemma (not the one in the exercise) in hand, we may now design a decider D for the language L of string encodings of DFA's that accept infinitely many strings. On input w, D first checks whether w encodes a DFA M. If not, D rejects w. If w encodes a valid DFA M, D starts by enumerating all strings of length less than 2p over the input alphabet of M. This requires only a finite amount of time since there are finitely many such strings over the finite input alphabet. D feeds each such string to M. For each accepted string, D determines whether the string is pumpable by checking for repeated states in the state trajectory of M on the given input string. If a pumpable accepted string is found, D accepts w. Otherwise D rejects w. This machine D is a decider that recognizes the target language L.
Now a general result about decidability and recognizability.
Theorem. A language L is Turing decidable if and only if both L and its complement are Turing recognizable.
Proof: As with any "if and only if" proof, we must prove two statements.
First assume that L is Turing decidable. We will show that L and L' are Turing recognizable. This is easy. Since L is Turing decidable, there is a Turing decider machine D (one that halts on all inputs) that recognizes L. This shows immediately that L is Turing recognizable. On the other hand, it is easy to construct a Turing machine D' that recognizes L'. Namely, on input w, D' feeds w to the original decider machine D and waits for D to finish processing w. Since D is a decider, this happens after a finite number of steps. We decree that if D accepts w, then D' rejects w, and if D rejects w, then D' accepts w. By design, D' recognizes L' (in fact D' decides L'). This shows that L' is Turing recognizable. The "only if" statement has now been proved.
Now assume that L and L' are Turing recognizable. We will show that L is decidable (by the way, L' will then also be decidable, as the proof of the "only if" direction above shows, but we don't really need to show that here). Construct a decider Turing machine D that recognizes L as follows. Let M and M' be Turing machines that recognize L and L' respectively. We don't know whether these machines are deciders or not, and we can't assume that they are. On input w, the decider D will feed w to both M and M'. D will then wait for one of the two machines to accept w. Can this wait last forever? No, because w is either in L or it's not, and in the latter case w must be in the complement L' of L (that's what the complement of L is - the set of all strings that are not in L). If w is in L, M will accept w. If w is not in L, M' will accept w. We decree that in the first case D will accept w and in the second case D will reject w. Since one of these two outcomes occurs after a finite number of steps, D decides L as desired. This completes the proof.