COMPSCI 350 FC, 2006
DECIDABLE LANGUAGES (section 4.1 Sipser)
We focus on decidable problems concerning regular languages.
We shall represent computational decision problems as problems about languages. Consider first the problem of deciding whether a particular finite automaton accepts a given string. This problem can be represented as the problem of whether the following language is (Turing-) decidable:
ADFA = {<B,w> | B is a DFA that accepts input string w}
Theorem 8 (= Theorem 4.1 Sipser) ADFA is a decidable language.
Proof: Consider the following machine, for which we give an implementation-level description:
M = “On an input of the form <B,w>, where B is a DFA and w a string over the alphabet of B, go to 1. (If the input is not of this form, reject.).
1. Simulate B on w.
2. If the simulation ends in an accept state, accept the input <B,w>. If it ends in a non-accepting state, reject.”
By construction, given input <B,w>, where B is a DFA and w a string over the alphabet of B, M accepts the input if B, presented with w, terminates its processing of w in accepting state, and rejects the input otherwise.
Let ANFA = {<B,w> | B is an NFA that accepts input string w}
Theorem 9 (= Theorem 4.2 Sipser) ANFA is a decidable language.
Proof: Consider the following machine, which uses M above as a subroutine:
N = “On input <B,w>, where B is a DFA and w a string over the alphabet of B,
1. Convert NFA B to an equivalent DFA C, using a fixed effective conversion procedure (eg, the one given in Theorem 1.19 [Sipser edition 1] =Theorem 1.39 [edition 2]), .
2. Run M on input <C,w>.
3. If M accepts, accept; otherwise, reject.”
By construction, given input <B,w>, where B is a NFA and w a string over the alphabet of B, N accepts the input if the equivalent DFA C, presented with w, terminates its processing of w in accepting state, and rejects the input otherwise.
Theorem 10 (=Theorem 4.4 Sipser) EDFA = {<B> | B is a DFA & L(B) = } is decidable.
Proof: A DFA accepts some string (ie, its language is non-empty) iff it is possible to reach an accept state from the start state by travelling along the transition arrows of the DFA.
T= “On input <B>,
- Mark the start state of B.
- Mark any state that has a transition coming into it from a marked state. If no new states get marked this way, go to 3. Else, go to 2 [ie, repeat].
- If no accept state is marked, accept. Otherwise, reject.”
T accepts <B> if no string is accepted by B, i.e., L(B) = , and rejects B otherwise. Hence T decides EFDA.
Theorem 11 (=Theorem 4.5 Sipser) EQDFA = {<A,B,> | A, B are DFAs & L(A) = L(B)} is decidable.
Proof: Suppose we are given DFAs A and B. Note that L(A) = L(B) iff L(A) L(B) and L(B) L(A). The latter two inclusions hold iff L(A) L(B)c = (ie, there is nothing in L(A) which is not also in L(B)) and L(B) L(A)c = (ie, there is nothing in L(B) which is not also in L(A)), where L(X)c is the complement of L(X). And this in turn is true iff the union of these two sets is also empty. In short,
(*) L(A) = L(B) iff ((L(A) L(B)c) (L(A)c L(B)) =
We will decide EQDFA by means of a Turing machine that tests whether L(A) = L(B) by testing whether ((L(A) L(B)c) (L(A)c L(B)) = , using the TM T constructed in the proof to Theorem 10. To see that there is such a decider for EQDFA, note that the proofs of the closure of the class of regular languages under intersection, complement, and union, yield an effective algorithm that, presented with DFAs A and B, result in a DFA C that recognises (L(A) L(B)c) (L(A)c L(B))). This algorithm can be carried out by a TM. Once we have such a C, we can test to see if L(A) = L(B) by testing to see if L(C) = , using the TM T of Theorem 10.
In short, we can decide EQDFA by means of the following decider E:
E = “On input <A,B>, where A and B are DFAs:
1. Construct a DFA C such that L(C) = iff ((L(A) L(B)c) (L(A)c L(B)).
2. Run TM T from Theorem 10 on input <C>.
3. If T accepts this input (ie, if L(C) ((L(A) L(B)c) (L(A)c L(B)) = , then accept. If T rejects, reject.”
Our final theorem in this section again uses the Turing machine T from the proof of Theorem 10 as a subroutine.
Theorem 12FINITEDFA = {<A> | A is a DFA & L(A) is finite} is decidable.
Proof: Consider the following Turing machine F:
F = “On input <A>,
- Determine the number k of states of A.
- Construct a DFA B over the same alphabet as A such B accepts all strings of length k or more .
- Construct a DFA C over the same alphabet as A such that L(C) = L(A) L(B).
- Run TM T from Theorem 10 on input <C>.
- If T accepts this input (ie, if L(C) = L(A) L(B) = , then accept. If T rejects, reject.”
To show that F decides FINITEDFA, we consider the two possibilities ‘L(A) is infinite’ and ‘L(A) is finite’ in turn. (i) Suppose first that L(A) is infinite. In this case, A accept arbitrarily long strings, so that it will share infinitely many strings with L(B), and hence L(A) L(B) . By construction, machine F will reject such an <A>. (ii) Now suppose that L(A) is finite. In this case, A accepts no string of length k or more, for if it did accept such a string such a string could be pumped to obtain infinitely many strings (using the method of the pumping lemma), and this would show that L(A) was infinite. Since A accepts no string of length k or more, it has no string in common with L(B), so that L(A) L(B) = , in which case F accepts input <A>.
In short, F accepts <A> if L(A) is finite, and rejects <A> otherwise. Hence F decides FINITEDFA.
------
UNDECIDABLE LANGUAGES (section 4.2, Sipser)
Remarkably, everything changes when we turn to decision problems involving Turing machines, for example whether an arbitrary Turing machine accepts a given string, whether it performs a given task, and so on. These problems turn out not to be decidable. Thus consider the first problem. This problem can be represented as a problem about whether a certain language ATM is Turing-decidable or not, where ATM = {<M,w> | M is a TM and M accepts w}. ATM is the Turing machine version of ADFA, which we know to be decidable (Theorem 8). (We can assume that ATM is based on Turing machines over any possible alphabet, as in the encoding method we used. Nothing of any importance changes if we restrict the alphabet to a fixed alphabet .)
Theorem13 ATM is Turing-recognisable.
Proof: Theorem 12 is an easy corollary of Theorem 5, the Universal Turing Machine Theorem. According to Theorem 5, there is a universal Turing machine which presented with <M,w> as input, where M is a Turing machine and w a string over the alphabetof halts in the accept state if M accepts w, halts in the reject state if M rejects w, and doesn’t halt if M doesn’t halt on w. therefore recognises the language ATM.
We now show that ATM is Turing-undecidable, pretty well following the proof in Sipser.
Theorem14 (= Theorem 4.11 Sipser) ATM is Turing-undecidable.
Proof: Assume ATM is Turing-decidable, contrary to what we are trying to prove. Suppose that H decides ATM. As a decider, H halts and accepts <M,w> if M accepts w, and H halts and rejects <M,w> if M does not accept w (it rejects all strings not of the form <M,w>). (We can represent H as follows:
H(<M,w>) = accept if M accepts w
reject if M does not accept w.)
We now construct a new Turing machine with H as subroutine. This new machine, which we dub ‘D’, for ‘Diagonaliser’ (we will see why in a moment), calls subroutine H to determine what M does when M is given the string <M> as argument, ie its own encoding, and then does the very opposite to what M does.
D = “On input <M>, where M is a TM,
- Run H on input <M,<M>.
- If H accepts this input (ie, M accepts <M>), then reject. If H rejects this input (ie, M does not accept <M>), then accept.”
We can represent D as follows:
D(<M>)= accept if M does not accept<M>
reject if M accepts<M>
Now consider what happens if we use <D> as input to D:
D(<D>)= accept if Ddoes not accept<D>
reject if D accepts<D>
Thus D accepts <D> iff D does not accept <D>. But this is a contradiction. Hence the assumption we began with, namely that ATM is Turing-decidable, is false. It follows that ATM is Turing-undecidable.
To see why this is called a proof by diagonalisation, consider first Theorem 7, which showed us that there are languages that are not Turing-recognisable. That construction proceeded as follows. Consider the 2-dimensional array
| L1 L2 L3 …
w1| no yes no …
w2| yes yes yes …
w3| yes no no …
… | … … … …
where the entry at row i and column j tells us whether wi Lj. Language L was defined by ensuring that a string wibelongs to L just when the diagonal at entry (i, i) says No (ie, just when wi Li), and doesn’t belong when it says Yes. If L is one of the Li, say Lk, this means that wk L just when wk L, a contradiction.
Turning now to the proof of Theorem 14, suppose that whether a Turing machine M accepts, rejects or fails to halt on its own code <M> is specified by the following 2-dimensional array.
| <M1> <M2 <M3> <M4> …
M1 | accept reject accept …
M2 | reject reject accept accept …
M3| …
M4| accept accept reject …
.
Assuming Turing machine H exists, the following figure then tells us the results of running H on input <Mi, <Mj>:
| <M1> <M2 <M3> <M4> …
M1| accept reject reject accept …
M2| reject reject accept accept …
M3| reject reject reject reject …
M4| accept accept reject reject …
.
Now consider D, which was deliberately made to behave differently on <M> from the way M behaved on < M > , as specified along the diagonal. D rejects <M> exactly when H accepts <M, <M>, ie ie exactly when M accepts <M>. Hence if D is one of the machines in this array, it follows that D rejects <D> exactly when D accepts <D>, a contradiction.
A TURING-UNRECOGNISABLE LANGUAGE
We already know, by Theorem 7, that there are Turing-unrecognisable languages, but so far we don’t know that any of them are theoretically very interesting. We now show that there are are theoretically interesting Turing-unrecognisable languages. We first prove a theorem relating decidability to recognisability.
Theorem 15 (=Theorem 4.23, Sipser) A language A is Turing-decidable iff both A and the complement of A are Turing-recognisable.
Proof: (a) : Suppose A is Turing-decidable. Then A is obviously Turing-recognisable (being decidable means that there is a decider that recognises the language). In addition, the complement Ac is also Turing-decidable (since the class of Turing-decidable languages is closed under complementation), so that Ac is also Turing-recognisable.
(b) : Suppose both A and the complement of A are Turing-recognisable. Let M1 recognise A and M2 the complement of A. Then M decides A, where
M = “On input w,
1. Run M1 and M2 on w in parallel, simulating one step of each machine in turn.
2. If M1 accepts, accept. If M2 accepts, reject.”
Either w is in A or in its complement, but not both. If the former, than since M1 recognises A, it accepts w. By construction, M then also accepts w. If the latter, then since M2 recognises the complement of A, it accepts w. By construction, M then rejects w. Hence M is a decider which accepts all strings in A and rejects all strings not in A. It follows that A is Turing-decidable.
Corollary: The complement of ATM is not Turing-recognisable.
Proof: We know, by Theorem 13, that ATM is Turing-recognisable. If the complement of ATM is Turing-recognisable, then by Theorem 15 ATM is Turing-decidable. But by Theorem 14 ATM is Turing-undecidable. It follows that the complement of ATM is not Turing-recognisable.
MORE ON UNDECIDABILITY
We are now ready to tackle the Halting problem for Turing machines. The method we will use is the method of reduction. Recall how we showed that the problem of deciding whether L(A) = L(B), where A and B are DFAs, was solvable by reducing it to the problem of deciding whether the language of a DFA is empty (we already knew we had a solution to that problem). This kind of reduction showed that the first problem was no harder than the second: a solution to the second yields a solution to the first.
We now show that a problem like the Halting problem is not solvable by showing that the problem of deciding whether a TM M accepts a string w is no harder: if we had a solution to the Halting problem, we would have a solution to this problem as well. Since we know that this problem is unsolvable (that is, we know that ATM is undecidable), it follows that the Halting problem is unsolvable as well.
Let HALTTM = {<M,w> | M is a TM that halts on input w}
Theorem 16 (=Theorem 5.1 Sipser) HALTTM is undecidable.
Proof: We show that ATM is reducible to HALTTM ; that is, that if we have a way of deciding HALTTM we also have a way of deciding ATM.
Suppose there is a TM R that decides HALTTM . We now use this machine to devise a TM S that decides ATM.
S = “On input <M,w>, where M is a TM M and w a string:
1. Run R on <M,w>.
2. If R accepts, simulate M on w until it halts; if M halts in an accepting configuration, accept, while if M halts in a rejectingconfiguration, reject.
3. If R rejects, reject.”
Clearly, if R decides HALTTM, then S decides ATM. But there can’t be such a TM S: ATM is undecidable. It follows that HALTTM must also be undecidable.
We now prove a bunch of other problems to be unsolvable. Some are in Sipser.
Recall that EDFA , EQDFA, REGULARDFA , FINITEDFAwere decidable.
Let ETM = {<M> | M is a TM and L(M) = },
EQTM = {<M,N> | M, N are TMs and L(M)=L(N)},
REGULARTM= {<M> | M is a TM and L(M) is regular}
FINITETM = {<M> | M is a TM and L(M) is finite}
Theorem 17 (a) ETM is undecidable.
(b) FINITETMis undecidable.
(c) REGULARTM is undecidable.
(d) EQTMis undecidable.
Proof:
(a)Suppose ETM is Turing-decidable. Let R decide ETM. We modify it to decide ATM. To decide ATM, we need a machine which, when given <M,w>, accepts this input if M accepts w and rejects this input if M does not accept w. Note that if, given M and w, we could devise a machine M1 such that L(M1) if M accepts w and L(M1) = otherwise, then we could use R to decide if M accepts w.
Here is such a machine: Given M and w, define
M1 = “On input x:
1. If x w, reject.
2. If x = w, run M on input w and accept if M does.”
Note that L(M1) = {w} if M accepts w, and L(M1) = otherwise.
We can now construct a TM S to decide ATM.
S = “On input <M,w>, where M is a TM M and w a string:
1. Use the encoded description of M to construct the TM M1 described above.
2. Run R on input <M1>.
3. If R accepts, reject. If R rejects, accept.”
(Note that it is important that such a S can compute a description of M1 from M and w; that it can do so follows from the fact that it need only add to M whatever is needed to do the ‘x=w’ test.)
Now,if R were a decider for ETM, S would be a decider for ATM. But there can be no such decider. Hence ETM is undecidable.
(b) Suppose FINITETM were decidable. Let R decide it. Much as for part (a), we construct a TM M2 with the property that L(M2) is notfinite iff M accepts w, for if there is such a TM we can use R to decide if M accepts w. The machine we use is, once again, based on M and w:
M2 = “On input x:
1. If x = w, reject.
2. If x w, run M on input w and accept if M
accepts w.”
Note that L(M2) is finite (and = ) if M does not accept w, and infinite otherwise.
We can now construct a TM S to decide ATM.
S = “On input <M,w>, where M is a TM and w a string:
1. Use the encoded description of M to construct the TM M2 described above.
2. Run R on input <M2>.
3. If R accepts, reject. If R rejects, accept.”
(Once again, S can compute a description of M2 from M and w; that it can do so follows from the fact that it need only add to M whatever is needed to do the ‘x=w’ test.)
If R were a decider for FINITETM, S would be a decider for ATM. But there can be no such decider. Hence FINITETM is undecidable.
(Note, by the way, that because L(M2) = iff M doesn’t accept w, we could have used M2 rather than M1 in the proof of part (a) above.)
(c) Suppose REGULARTM is decidable, and that R decides it. We construct a machine M3 from M and w such that the language of this machine is regular iff M accepts w.
The idea is simple:
M3 = “On input x:
1. If x is of the form 0n1n, accept.
2. If x is not of this form, run M on w. Accept if M accepts w.”
Clearly, if M accepts w, then M3 accepts all strings, so that L(M3) is regular. But if M doesn’t accept w, then L(M3) = {0n1n | n 0}, which is non-regular.
We are now ready to build our decider for ATM.
S = “On input <M,w>, where M is a TM and w a string,
1. Use the encoded description of M to construct the TM M3 described above.
2. Run R on input <M3>.
3. If R accepts, accept. If R rejects, reject.”
(d) For the last part of the theorem, we use one of the languages already shown undecidable.
Suppose EQTM is decidable, and let R decide it. Then we can use decide ETM as follows. Given <M>, simply test it against the code of some given machine whose language is known to be empty, using R. Let M* be such a machine.
In short,
S = “On input <M>:
1. Run R on <M,M*>.
2. If R accepts, accept. If R rejects, reject.”
Clearly, if R decides EQTM then S decides ETM. Since ETM is undecidable, it follows that EQTM is undecidable.
That completes the proof. The style of proof used may lead one to think that the problemof whetherthe languageof an arbitrary Turing machine has a certain property (eg, whether it is empty or not) is always undecidable, ie that any language of the formL = {<M> | L(M) has property P} is undecidable. But this is not quite true. Let La = {<M> | L(M) is either finite or infinite} and Lb = {<M> | L(M) is both finite and infinite}. We might call these languages trivial. They contain (codes of) all Turing machines whatsoever (in the case of La) or (codes of) no Turing machines (Lb). And clearly trivial languages are decidable.
But there is an important pattern: apart from trivial languages, it is true that the problemof whetherthe languageof an arbitrary Turing machine has a certain property is undecidable.
Theorem 18(RICE’S THEOREM, first proved by Gordon Rice in 1953 for classes of partial recursive functions): Given a non-trivial class C = {<M> | L(M) has property P}, C is undecidable.
(Note: to say that a language L(M) has a property P is to say that if L(M) = L(N), then L(N) also has property P. Hence if <M> is in C and L(M) = L(N) then <N> is also in C )
Proof: Suppose C is decidable, and that R decides C. Let M* be a fixed TM whose language is empty. We can suppose, without loss of generality, that <M*> is not in C.[1] Now, since C is non-trivial, there is a TM T such that <T> is in C.
We claim that, given M and w, we can effectively construct a TM M4 with the following feature: <M4> is in C iff M accepts w.
M4 = “On input x:
1. Run M on w. If it rejects, reject. If it accepts, go to 2.
2. Simulate T on x. If it accepts, accept.”
Clearly, if M accepts w then L(M4) = L(T). And if M doesn’t accept w, then no string x is accepted by M4, ie L(M4) = = L(M*). Given that <T> is in C but <M*> is not, this shows that <M4> is in C precisely when M accepts w.
The rest of the proof is easy. The following machine now decides ATM:
S = “On input <M,W>, where M is a TM and w a string:
1. Use M and w to construct the machine M4 described above.
2. Run R on <M4>.
3. If R accepts, accept. If R rejects, reject.”
Clearly, if R decides C then S decides ATM. Since ATM is undecidable, it follows that C is undecidable.
1
[1] If <M*>is in C, then it is not in the complement of C, and we can deal with the complement of C instead. Note that if C is decidable and non-trivial, then so is the complement of C..