1610906232-7ba7dbaea13262b50a6029d682cb7f1b (824370), страница 54
Текст из файла (страница 54)
Show that the following problem issolvable: Given a Turing machine M and an input string w, does Musef(lwl) tape squares on input w?(c) Show that the following problem is undecidable: Given a Turing machine.U and an input string w. does there exist a k 2: 0 such that M does notuse k tape squares on input w? (That is, does M use a finite amount oftape on input w?)5.4.2. Which of the following problems about Turing machines are solvable, andwhich are undecidable? Explain your answers carefully.(a) To determine, given a Turing machine M, a state q, and a string w, whetherM ever reaches state q when started with input w from its initial state.(b) To determine, given a Turing machine M and two states p and q, whetherthere is any configuration with state p which yields a configuration withstate q, where p is a particular state of M.(c) To determine, given a Turing machine M and a state q, whether there isany configuration at all that yields a configuration with state q.(d) To determine, given a Turing machine M and a symbol a, whether M everwrites the symbol a when started on the empty tape.(e) To determine, given a Turing machine M, whether M ever writes a nonblanksymbol when started on the empty tape.(f) To determine, given a Turing machine M and a string w, whether M evermoves its head to the left when started with input '/L'.(g) To determine, given two Turing machines, whether one semidecides thecomplement of the language semidecided by the other.(h) To determine, given two Turing machines, whether there is any string onwhich they both halt.(i) To determine, given a Turing machine M, whether the language semidecidedby M is finite,5.4.3.
Show that it is an undecidable problem to determine, given a Turing machine M, whether there is some string w such that M enters each of itsstates during its computation on input w.5.4.4. Show that the halting problem for Turing machines remains undecidableeven when restricted to Turing machines with some small, fixed number ofstates. (If the number is required to be fixed but not small, the existenceof a universal Turing machine establishes the result, Show how any Turingmachine can be simulated, in some suitable sense, by a Turing machinewith about half a dozen states but a much larger alphabet. Actually, threestates are enough; in fact, two would be enough if we allowed our machinesto write and move in a single step.)258Chapter 5: UNDECIDABILITY5.4.5.
Show that any Turing machine can be simulated, in some sense we leave itto you to specify, by an automaton with no tape hut with two counters.A counter is a pushdown store with only one symbol, except for a distinguishable bottom-marker, which is never removed. Thus a counter may bethought of as a register for containing a number in unary. The possibleoperations on a counter are the following: add 1; see if it contains 0; andif it does not contain 0, subtract 1.
Conclude that the halting problem forthese 2-counter machines is undecidable. (Hint: Start by showing how tosimulate a Turing machine tape hy two push-down stores with two symbols; show that these can be simulated by four counters, by encoding thepushdown store contents in unary; finally, simulate four counters hy two,hy encoding four numbers a,b,c,d as 2a 3 b 5 c 7 d .)5.5UNSOLVABLE PROBLEMS ABOUT GRAMMARSUnsolvable prohlems do not occur only in the domain of Turing machines, butin virtually all fields of mathematics.
For example, there are several undecidableproblems related to grammars, summarized below.Theorem 5.5.1: Each of the following problems is undecidable.(a)(b)(c)(d)(e)For a given grammar G and string w, to determine whether wE L(G).For a given grammar G, to determine whether e E L( G) .For two given grammars G 1 and G 2 , to determine whether L(Gd = L(G 2 ).For an arbitrary grammar G, to determine whether' L(G) = 0.Furthermore, ther'e is a certain fixed grammar Go, such that it is undecidableto determine whether any given string w is in L( Go).Proof: We shall show a reduction from the halting prohlem to (a); very similarreductions establish the remaining parts. Given any Turing machine M andstring w, we simply apply to M the construction given in the proof of Theorem4.6.1 to produce a grammar G such that L(G) is the language semi decided byM.
It follows that w E L(G) if and only if M halts on input w . •Since we had already established that grammars are exactly as powerfulas Turing machines (Theorem 4.6.1), the undecidability results above probablycame as no surprise. What is much more astonishing, however, is that similarquestions about context-free grammars and related systems -a rather simple andlimited domain- are undecidable. Naturally, the undecidable problems cannotinclude telling whether wE L(G), or whether L(G) = 0 -these problems can besolved by algorithms, and in fact efficient ones (recall Theorem 3.6.1).
Severalother problems, however, are not solvable.5.5: Unsolvable Problems about Grammars259Theorem 5.5.2: Each of the following problems is undecidable.(a) Given a context-free grammar G, is L(G) = ~'?(b) Given two context-free grammars G I and G 2 , is L(Gd = L(G 2 )?(c) Given two pushdown automata ;1h and ;U2 , do they accept precisely thesame language?(d) Given a pushdown automaton M, find an equivalent pushdown automatonwith as few states as possible.Proof: (a) The main technical difficulty is in proving Part (a); the other partsfollow rather easily.
We shall reduce to Part (a) the prohlem shown to be undecidable in Part (d) of Theorem 5.5.1, that is, the problem of deciding whether agiven generalized grammar generates any string at all.Let G I = (VI, ~l, R I , Sd be a generalized grammar. We first modify thisgrammar as follows: Let the rules of G I be O!i --+ !3i, for i = 1, ...
, IRII. Weadd to VI IRII new nonterminal symbols Ai, i = 1, ... , IRII, one for each rulein R I , and replace the ith rule, for i = 1, ... , IRII, by the two rules O!i --+ Aiand Ai --+ !3i. Let us call the resulting grammar G~ = (V!,~I,R~,Sd. It isclear that L(GD = L(Gd; any derivation of a string in G I can be turned into astandard derivation of the same string in G~, in which each odd step appliesa rule of the form Ui --+ Ai, while the subsequent even step applies a rule of theform Ai --+ vi·From G~ we shall construct a context-free grammar G 2 over an alphabet~ such that L(G 2 ) = ~.
if and only L(GI) = 0. This reduction would thenestablish Part (a).Suppose that there is a derivation of a terminal string in G~; by the remarkabove, we can assume that it is a standard derivation, namely,where Xi E V!* for all i, and Xn E ~i, n is even, each Xi with i odd contains exactly one Aj nonterminal, while each Xi with i even contains no Aj nonterminal.Such a derivation can be represented as a string in the alphabet ~ = V u {=>},precisdy the string displayed above. In fact, for reasons that will be clear soon,we shall be more interested in the boustrophedon version t of the string thatcorresponds to the standard derivation, in which the odd-numbered Xi'S Xl, X3,etc. are reversed:tBoustrophedon, from a Greek word meaning "as the ox turns," is a way of writingalternate lines in opposite direction, from left to right and from right to left.260Chapter 5: UNDECIDABILITYConsider now the language Dc~ ~ ~* consisting of all such boustrophedonversions of standard derivations of terminal strings in G~.
It is dear that Dc\ =if and only if L(Gd = 0. To put it otherwise, in terms of the complementDc'1 = ~* - Dc"oDc~ = ~*if and only if L(Gd= 0.Therefore, all we have to show in order to conclude the proof is that Dc'1 iscontext-free.To this end, let us look closer at the language Dc"1 What does it take fora string w to be in this language? That is, when does a string 1V fail to be aboustrophedon version of a standard derivation of a terminal string in G~? Itdoes if and only if at least one of the following conditions holds:(1)(2)(3)(4)does not start with 51 :::}.does not end with:::} v, where v E ~~.1V contains an odd number of :::}'s.1V is of the form u :::} y :::} v or u :::} y, where(a) u contains an even number of occurrences of:::},(b) y contains exactly one occurrence of :::}, and(c) y is not of the form y = Y1 A i Y2 :::} yf (3iYr for some i :::; JR1J andY1, Y2 E ~r, where (3i is the right-hand side of the ith rule of G 1·(5) 1V is of the form u:::} Y :::} v, where(a) u contains an odd number of occurrf'llces of:::},(b) Y contains exactly one occurrence of :::}, and(c) Y is not of the form Y = Y1CJ:iY2 :::} yf Aiyr for some i :::; JR1J andY1, Y2 E ~r, where CJ:i is the left-hand side of the ith rule of G 1·1V1VIf 1V satisfies anyone of these five conditions, and only then, 1V is in Dc'1 .That is, Dc'1 is the union of the five languages L 1 , L 2 , L3, L 4 , and L5 describedin (1) through (5) above.
We claim that all five languages are context-free, andin fact that we can construct context-free grammars that generate them. Forthe first three, which happen to be regular languages, this is trivial.For L4 and L 5 , our argument is indirect: We shall argue that we can designa nondeterministic pushdown automaton for each, and rely on Theorem 3.6.1Part (b), stating that there is an algorithm for constructing from any pushdownautomaton M a context-free grammar G such that L(G) = L(M).The pushdown automaton M4 accepting L4 works in two phases. In thefirst phase, it scans input 1V from left to right, always remembering whether ithas seen an odd or even number of :::}'s (this can be accomplished by two states).When an even-numbered:::} is encountered, M4 has two options, and choosesbetween them nondeterministically: It can either continue to count :::}'s modulotwo, or it can enter the second phase.5.5: Unsolvable Problems about Grammars261In the second phase, M4 accumulates its input in its stack until a :::} isfound.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
