1610906232-7ba7dbaea13262b50a6029d682cb7f1b (824370), страница 53

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 53)

We have a full-fledgednotation for algorithms, a "programming language" of sorts: the Turing machine. In fact, in the last section we introduced one last feature we need: wehave developed a framework that allows our "programs" to manipulate otherprograms and their inputs -exactly as our fictitious program halts(P, X) does.We are thus ready to define a language that is not recursive, and prove that itis not. LetH = {"M" "w" : Thring machine M halts on input string w}.Notice first that H is recursively enumerable: It is precisely the language semidecided by our universal Turing machine U in the previous section. Indeed, oninput "M" "w", U halts precisely when the input is in H.252Chapter 5: UNDECIDABILITYF\irthermore, if H is recursive, then every recursively enumerable languageis recursive. In other words, H holds the key to the question we asked in Section4.2, whether all recursively enumerable languages are also Turing decidable:the answer is positive if and only if H is recursive.

For suppose that H isindeed decided by some Turing machine Mo. Then given any particular Turingmachine M semi deciding a language L(M), we could design a Turing machineM' that decides L(M) as follows: First, M' transforms its input tape fromc> U wl,J to c>"M" "w"l,J and then simulates Mo on this input.

By hypothesis, Mowill correctly decide whether or not M accepts w. Anticipating the issues dealtwith in Chapter 7, we could say that there are reductions from all recursivelyenumerable languages to H, and thus H is complete for the class of recursivelyenumerable languages.But we can show, by formalizing the argument for halts(P, X) above, thatH is not recursive. First, if H were recursive, thenHi = {"M" : Turing machine M halts on input string "M"}would also be recursive. (Hi stands for the halts(X, X) part of the diagonalprogram.) If there were a Turing machine Mo that could decide H, then aTuring machine Mi to decide Hi would only need to transform its input stringc> U "AI"U to c> U "AI" "M"u and then yield control to Alo. Therefore, it sufficesto show that Hi is not recursive.Second, if Hi, were recursive, then its complement would also be recursive:Hi= {w : either wis not the encoding of a Turing machine, or it isthe encoding "M" of a Turing machine~Mthat does not halt on "M"}.This is so because the class of recursive languages is closed under complement(Theorem 4.2.2).

Incidentally, Hi is the diagonal language, the analog of ourdiagonal program, and the last act of the proof.But Hi cannot even be recursively enumerable ~let alone recursive. Forsuppose AJ* were a Turing machine that semi decided Hi. Is "M*" in Hi? Bydefinition of Hi, "AI*" E Hi if and only if M* does not accept input string"AI*". But M* is supposed to semidecide Hi, so "!v!*" E Hi if and only if M*accepts "M*". We have concluded that M* accepts "AI*" if and only if M*does not accept "M*". This is absurd, so the assumption that Mo exists musthave been in error.Let us summarize the development of this section.

We wanted to discoverwhether every recursively enumerable language is recursive. We observed thatthis would be true if and only if the particular recursively enumerable languageH were recursive. From H we derived, in two steps, the language Hi, which hasto be recursive in order for H to be recursive. But the assumption that Hi isrecursive led to a logical contradiction, by diagonalization. We have thereforeproved the following most important theorem.2535.3: The Halting ProblemTheorem 5.3.1: The language H is not recursive; therefore, the class of recursive languages is a strict subset of the class of recursively enumerable languages.We said earlier that this argument is an instance of the diagonalizationprinciple used in Section 1.5 to show that 2N is not countable.

To see why,and to underscore one more time the essence of the proof, let us define a binaryrelation R on strings over the alphabet used for the encoding of TUring machines:(u, w) E R if and only if u = "M" for some Turing machine M that accepts w.(R is a version of H.) Now let, for each string u,Ru = {w : (u, w) E R}(the Ru's correspond to the recursively enumerable languages), and consider thediagonal of R, that is,D={w:(w,w)~R}(D is Hd. By the diagonalization principle, D -:j:. Ru for all u; that is, HI is alanguage different from any recursively enumerable language.And why is D -:j:. Ru for any u? Because D differs, by its very construction,from each Ru (and therefore from each recursively enumerable language) on atleast one string -namely, u.Theorem 5.3.1 answers negatively the first of the two questions we posedin the end of Section 4.2 ("is every recursively enumerable language also recursive?" and "is the class of recursively enumerable languages closed undercomplement?").

But the same proof supplies the answer to the other question.It is easy to see that HI, like H, is recursively enumerable, and we have shownthat HI is not recursively enumerable. Therefore we have also proved the following result.Theorem 5.3.2: The class of recursively enumerable languages is not closedunder complement.Problems for Section 5.35.3.1. We can find a particular example of a nonrecursive function without usinga diagonal argument. The busy-beaver function (3 : N f-+ N is definedas follows: For each integer n, (3(n) is the largest number m such that thereis a Turing machine with alphabet {t>, U, a, b} and with exactly n stateswhich, when started with the blank tape, eventually halts at configuration(h, t>1Ja m ).(a) Show that, if f is any recursive function, then there is an integer kf suchthat (3(n + k f ) 2: f(n). (k f is the number of states in the Turing machineMf, which, when started with input an, halts with af(n) on its tape.)254Chapter 5: UNDECIDABILITY(b) Show that f3 is not recursive.

(Suppose it were; then so would be(1(2n). Apply the result in (a) above.)f (n)5.3.2. We know that the class of recursively enumerable languages is not closedunder complementation. Show that it is closed under union and intersection.5.3.3. Show that the class of recursive languages is closed under union, complementation, intersection, concatenation, and Kleene star.5.4UNDECIDABLE PROBLEMS ABOUT TURING MACHINESWe have proved a momentous result. Let us back off a bit and see what itsays on the intuitive level, in light of the Church-Turing thesis. Since the proofestablishes that H is not recursive, and we have accepted the principle that anyalgorithm can be turned into a Turing machine that halts on all inputs, we mustconclude that there is no algorithm that decides, for an arbitrary given Turingmachine AI and input string w, whether or not M accepts w. Problems forwhich no algorithms exist are called undecidable or unsolvable; we shall seemany of them in this chapter.

The most famous and fundamental undecidableproblem is the one of telling whether a given Turing machine halts on a giveninput ~whose undecidability we just established. This problem is usually calledthe halting problem for Turing machines.Note that the undecidability of the halting problem in no way implies thatthere may not be some circumstances under which it is possible to predictwhether a Turing machine will halt on an input string. In Example 4.1.2 wewere able to conclude that a certain simple machine is bound to never halt on acertain input.

Or we might examine the transition table of the Turing machine,for example, to check whether a halt state is anywhere represented; if not, themachine cannot halt on any input string. This and more complex analyses mayyield some useful information for certain cases; but our theorem implies that anysuch analysis must ultimately either be inconclusive or yield incorrect results:There is no completely general method that correctly decides all cases.Once we have established, by diagonalization, that the halting problem isundecidable, the undecidability of a great variety of problems follows.

Theseresults are proved not by further diagonalizations, but by reductions: we showin each case that if some language L2 were recursive, then so would be somelanguage L 1 , already known not to be recursive.Definition 5.4.1: Let L 1 ,L2 ~is a recursive fUIlction T : ~. r--+~*~.be languages. A reduction from Ll to L2such that x ELl if and only if T(X) E L 2.5.4: Undecidable Problems about Turing Machines255The reader must take care to understand the "direction" in which a reduction is to be applied. To show that a language L2 is not recursive, we mustidentify a language L1 that is known to be not recursive, and then reduce L1 toL 2.

To reduce L2 to L1 would achieve nothing: it would merely show that L2could be decided if we could decide L1 -which we know we cannot.Formally, the correct use of reductions in proofs of undecidability is thefollowing:Theorem 5.4.1: If L1 is not recursive, and there is a reduction from L1 to L 2,then L2 is also not recursive.Proof: Suppose that L2 is recursive, say decided by Turing machine M 2 , andlet T be the Turing machine that computes the reduction T. Then the Turingmachine T M2 would decide L 1. But L1 is undecidable -a contradiction .•We next use reductions to show that several problems about Turing machines are undecidable.Theorem 5.4.2: The following problems about Turing machines are undecidable.(a) Given a Turing machine M and an input string w, does M halt on inputw?(b) Given a Turing machine M, does M halt on the empty tape?(c) Given a Turing machine M, is there any string at all on which M halts?(d) Given a Turing machine M, does M halt on every input string?(e) Given two Turing machines M1 and M 2, do they halt on the same inputstrings?(f) Given a Turing machine M, is the language that M semidecides regular?Is it context-free? Is it recursive?(g) Furthermore, there is a certain fixed machine M, for which the followingproblem is undecidable: Given w, does M halt on w?Proof: Part (a) was proved in the previous section.(b) We describe a reduction from H to the languageL = {"M" : M halts on e}.Given the description of a Turing machine M and an input x, our reductionsimply constructs the description of a Turing machine Mw that operates asfollows: M w , when started on the empty tape (that is, in configuration (s, t>W),writes w on its tape and then starts to simulate M.

In other words, if w =a1 ... an, then Mw is simply the machineChapter 5: UNDECIDABILITY256And it is easy to see that the functionrecursive.Tthat maps "M" "w" to "Alw" is indeed(c) We can reduce the language L shown to be nonrecursive in Part (b) tothe language V = {"M" : M halts on some input}, as follows. Given the representation of any Turing machine 11.1, our reduction constructs the representationof a Turing machine M' that erases any input it is given, and then simulates Mon the empty string.

Clearly, M' halts on some string if and only if it halts onall strings, if and only if M halts on the empty string.(d) The argument for Part (c) works here as well, since M' is constructedso that it accepts some input if and only if it accepts every input.(e) We shall reduce the problem in Part (d) to this one.

Given the description of a machine M, our reduction constructs the stringT("M") = "M""y",where "y" is the description of the machine that immediately accepts any input.Clearly, the two machines M and y accept the same inputs if and only if Maccepts all inputs.(f) We reduce the problem in Part (b) above to the present one. We showhow to modify any Turing machine M to obtain a Turing machine M' such thatM' halts either on the strings in H or on no strings, depending on whether Mhalts on the empty string or not.

Since there is no algorithm for telling whetherM halts on the empty string, there can be none for telling whether L(M) is 0(which is regular, context-free, and recursive) or H (which is none of the three).First, M' saves its input string and initiates whatever M would do on inpute. When and if M would halt, M' restores its input and carries out on thatinput the operation of the universal Turing machine U. Thus M' either haltson no input, because it never finishes imitating M on input e, or else it halts onprecisely the strings in H.(g) The fixed machine Mo alluded to in the statement of the theorem isprecisely the universal Turing machine U .•Problems for Section 5.45.4.1. Say that Turing machine Muses k tape squares on input string w if andonly if there is a configuration of M, (q, uQ,v), such that (s, t>lJw) f-Af (q, uQ,v)and Iuavi 2: k.(a) Show that the following problem is solvable: Given a Turing machine M,an input string w, and a number k, does AI use k tape squares on input w?5.4: Undecidable Problems about Turing Machines257(b) Suppose that f : N f-t N is recursive.

Характеристики

Список файлов решённой задачи