1610906232-7ba7dbaea13262b50a6029d682cb7f1b (824370), страница 57
Текст из файла (страница 57)
Then the followingTuring machine MI (which was our first unsuccessful attempt at proving thesame direction of Theorem 5.7.2) lexicographically enumerates L: MI generatesone after the other in lexicographic order all strings in the alphabet of L, andruns M on each. Whenever M accepts, MI displays the string and continuesto the next one. If M rejects, AIl simply continues to the next string withoutpassing through the display state.For the other direction, suppose that L is lexicographically enumerated bya Turing machine M. There are two cases: If L is finite, then there is nothing toprove, since in this case L is certainly recursive (as well as context-free, regular,etc.).
So, suppose that L is infinite. The following machine MI decides L: Oninput w, start the enumerating machine M. Wait until either w is displayed, orany string that comes lexicographically after w is displayed. In the first case,accept w; in the second, reject. Since there are finitely many strings that comelexicographically before w (fewer than II: + lllwl) and L is infinite, we know thatone of the two will happen .•Every Turing machine M semidecides a unique language denoted L(M)-namely, the set of all inputs on which it halts. But L(M) is semidecidedby many other Turing machines, ranging from trivial perturbations of M (for270Chapter 5: UNDECIDABILITYexample, a version of M with its states renumbered, or a machine that performsa meaningless "dance" into new states just before halting, and is otherwiseidentical to M) to very subtle variants (the reader should be able to supplya few).
In other words, this function from the set of all Thring machines tothe class of recursively enumerable languages is far from an isomorphism, as itmaps an infinity of wildly different machines to the same language. In fact, weknow that it is undecidable whether two given machines are mapped to the samelanguage by this mapping. The following result suggests that this mapping is socomplicated, that, in some sense made precise below, all conceivable problemsabout it are undecidable.Theorem 5.7.4 (Rice's Theorem): Suppose that C is a proper, nonemptysubset of the class of all recursively enumerable languages.
Then the followingproblem is undecidable: Given a Turing machine M, is L(M) E C?Proof: We can assume that 0 ¢ C (otherwise, repeat the rest of the argumentfor the class of all recursively enumerable languages not in C, which is also aproper, nonempty subset of the recursively enumerable languages). Next, sinceC is nonempty, we can assume that there is a language L E C semidecided bymachine ML.We shall reduce the halting problem to the problem of deciding whetherthe language semi decided by a given Thring machine is in C. Suppose then thatwe are given a Turing machine M, and input w, and we wish to decide whetherM halts on w. To accomplish this, we construct a 1\uing machine TM,w, suchthat the language semi decided by TM,w is either the language L fixed above orthe language 0.
On input x, TM,w simulates the universal Turing machine U oninput "AI" "w". If it halts, then TM,w, instead of halting, goes on to simulateML on input x: It either halts and accepts, or never halts, depending on thebehavior of ML on x. Naturally, if U("M" "w") =/, TM,w(X) =/ as well. Toreview, TM,w is this machine:TM,w(x) : if U("M" "w") ::f./ then ML(x) else /Claim: The language semidecided by TM,w is in class C if and only if M haltson input w.Notice that the claim states that the construction of TM,w from M and w isa reduction of the halting problem to the problem of telling, given a Turingmachine, whether the language semidecided by it is in C.
This would concludethe proof of the theoremProof of the claim: Suppose that M halts on input w. Then TM,w on inputx determines this, and then always goes on to accept x if and only if x E L.Hence, in this case, the language semidecided by TM,w is L -which is in C.5.7: Properties of Recursive Languages271Suppose then that M(w) =/. In this case TM,w never halts, and thus Mxsemidecides the language 0, known not to be in C.•The undecidability of many problems follow from Rice's Theorem: Given aTuring machine M, is the language semidecided by it, L(M), regular? contextfree? finite? empty? ~*? recursive? -and so OILProblems for Section 5.75.7.1.
Show that L is recursively enumerable if and only if, for some nondeterministic Turing machine M, L = {w : (8 I> W I-M (h,l>!d.w)},wheres is the initiastate of M.5.7.2. Show that if a language is recursively enumerable, then there is a Turingmachine that enumerates it without ever repeating an element of the language.5.7.3. (a) Let ~ be an alphabet not containing the symbol ";", and suppose thatL ~ ~*; ~* is recursively enumerable. Show that the language L' = {x E~* : x; y E L for some y E ~*} is recursively enumerable.(b) Is L' in (a) necessarily recursive if L is recursive?5.7.4. A grammar is said to be context-sensitive if and only if each rule is ofthe form u -+ v , where Ivl 2: lui. A context-sensitive language is onegenerated by a context-sensitive grammar.(a) Show that every context-sensitive language is recursive.
(Hint: How longcan derivations be?)(b) Show that a language is context-sensitive if and only if it is generated bya grammar such that every rule is of the form uAv -+ uwv, where A is anonterminal, and w I- e.(c) An in-place acceptor (or linear-bounded automaton) is a nondeterministic Turing machine such that the tape head never visits a blank squareexcept for the two immediately to the right and to the left of the input. Showthat a language is context-sensitive if and only if it is semidecided by anin-place acceptor. (Hint: Both directions are specializations of the proof ofTheorem 4.6.1.)5.7.5.
The class of context-sensitive languages introduced in the previous problem, and characterized alternatively by nondeterministic in-place Turingacceptors in Part (c) above, completes the Chomsky hierarchy, an influential framework for thinking about the expressiveness of language generators and the power of automata, proposed by the linguist Noam Chomskyin the 1960s. The Chomsky hierarchy consists of these five classes of languages, in the order in which they were introduced in this book: regular languages, context-free languages, recursive languages, recursively enumerable272Chapter 5: UNDECIDABILITYlanguages, context-sensitive languages.
Arrange these classes of languagpsin order of increasing generality (so that each class in the list properly includes all previous ones), and write next to each the corresponding class ofautomata and/or grammars.5.7.6. Suppose that f : ~o 1--+ ~i is a recursive onto function. Show that there isa recursive function g : ~i 1--+ ~o such that f(g(w)) = w for each w E ~o·5.7.7.
Show that it is undecidable to tell whether the language semidecided by agi ven Turing machine is(a) finite.(b) regular.(c) context-free.(d) recursive.(e) equal to the language {ww R : wE {a,b}*}.5.7.8. The nonrecursive languages L exhibited in this chapter havp the propertythat either L or L is recursively enumerable.(a) Show by a counting argument that there is a language L such that neitherL nor L is recursively enumerable.(b) Give an example of such a language.5.7.9. This problem continues Problem 3.i.1D: Extend the Venn diagram of the(a) regular, (b) context-free, (c) deterministic context-free, and (d) complements of context-free languages, to include the following three new classes:(e) recursi ve,(f) recursively enumerable,(g) complements of recursively enumerable languages.Give an example of a language in each region of the Venn diagram.5.7.10.
Describe a Turing machine M that has the property that, on any input,it outputs "M" -its own description. (Hint: First write a program ina programming language that prints itself. Or, for a more complicatedargument, see the next problem.)5.7.11. (a) Argue that there is a Turing machine G which, when presented with thedescription of a Turing machine M. it computes the description of anotherTuring machine M2, which on any input x first simulates M on input "M",and then, if M halts with a valid description of a Turing machine N on itstape, it simulates N OIl input x.(b) Argue that there is a Turing machine C which, when presented withthe description of two Turing machines Ml and M 2 • it computes the Turingmachine that is the composition of Ml and M2; that is, the machine which,on any input x, first simulates M2 on x, and then it simulates Ml on theresult.273References(c) Suppose that M is a Turing machine which, when its input is a validdescription of a Turing machine, it outputs another valid description of aTuring machine.
Show that any such M has a jixpoint, that is, a Turing machine F with the property that F and the machine represented by M ("F")behave exactly the same on all inputs. (Suppose that the composition recall Part (b)- of M and G -recall Part (a)- is presented as an inputto G. Check that the machine whose description is output is the requiredfixpoint F.)(d) Let M be any Turing machine. Argue that there is another Turingmachine M' with the following property: For any input x, if M halts oninput x with output y, then M' also halts on input x, and its output isy"M'" -that is, M' pads the output of M with its own description, its"signat ure."REFERENCESThe undecidability of the halting problem was pr'oved by A.
M. Turing in his 1936 paperreferenced in the pr'cvious chapter. The undecidability of problems related to contextfree grammars was proved in the paper by Bar-Hilel, Perles, and Shamir cited at theend of Chapter 3. 1'ost's correspondence problem (see Problem 5.5.2) is fromo E. L. Post "A variant of a recursively unsolvable problem," Bulletin of the Americal Math.
Society, 52, pp. 264-268, 1946.The Chomsky hierarchy (see Problem 5.7.5) is due to Noam Chomskyo N. Chomsky "Three models for the description of language," IRE Transactionson Information Theory, 2, 3, pp.113-124, 1956.The tiling problem (Section 5.6) is fromo H. Wang "Proving theorems by pattern recognition," Bell System TechnicalJournal, 40, pp. 1-141,1961.For many more unsolvable problems, see the rcjerences of the last chapter", especiallythe books by Marlin Davis.6Computational Complexity6.1 THE CLASS PIn the previous chapter we saw that there exist well-defined decision problemsthat cannot be solved by algorithms, and gave some specific examples of suchproblems.
We can therefore classify all computational problems into two categories: those that can be solved by algorithms, and those that cannot. Withthe great advances in computer technology of the last few decades, one mayreasonably expect that all the problems of the former type can now be solved ina satisfactory way. Unfortunately, computing practice reveals that many problems, although in principle solvable, cannot be solved in any practical sense bycomputers due to excessive time requirements.Suppose that it is your task to schedule the visits of a traveling sales representative to 10 regional offices. You are given a map with the 10 cities anddistances in miles, and you are asked to produce the itinerary that minimizesthe total distance traversed.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
