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

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

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

We say that M decides a language L ~ (~- {C>, u})* if the followingtwo conditions hold for all w E (~ - {C>, u} )*:(a) There is a natural number N, depending on MaJid w, such that there isno configuration C satisfying (s, c>LJw) f-z. C.(b) wE L if and only if (s,c>LJw) f-~f (Y,uQv) for some U,V E ~*,a E~.Finally, we say that M computes a function f : (~ - {C>, U})*{C>, U})* if the following two conditions hold for all w E (~ - {C>, U} )*:rl (~­(a) There is an N, depending on M and w, such that there is no configurationC satisfying (s, c>LJw) f-z. C.(b) (s, C>LJw) f-M (h, uQv) if and only if ua = c>U, and v = f(w).These definitions reflect the difficulties associated with computing by nondeterministic Turing machines. First notice that, for a nondeterministic machineto decide a language and compute a fUIlction, we require that all of its computations halt; we achieve this by postulating that there is no computation continuingafter N steps, where N is an "upper bound" depending on the machine and theinput (this is condition (a) above).

Second, for M to decide a language, weonly require that at least one of its possible computations end up accepting theinput. Some, most, or all of the remaining computations could end up rejecting~the machine accepts by the force of this single accepting computation. Thisis a very unusual, asymmetric, and counterintuitive convention. For example, to4.5: Nondeterministic Turing Machines223create a machine that decides the complement of the language, it is not enoughto reverse the roles of the y and n states (since the machine may have both accepting and rejecting computations for some inputs).

As with nondeterministicfinite automata, to show that the class of languages decided by nondeterministicTuring machines is closed under complement, we must go through an equivalentdeterministic Turing machine ~and our main result in this section (Theorem4.5.1) states that an equivalent deterministic Turing machine must exist.Finally, for a nondeterministic Turing machine to compute a function, werequire that all possible computations agree on the outcome. If not, we wouldnot be able to decide which one is the right value of the function (in the cases ofdeciding or semi deciding a language, we resolve this uncertainty by postulatingthat the positive answer prevails).Before showing that nondeterminism, like the features considered in the previous sections, can be eliminated from Turing machines, let us consider a classicexample that demonstrates the power of nondeterminism in Turing machines asa conceptual device.Example 4.5.1: A composite number is one that is the product of twonatural numbers, each greater than one; for example, 4, 6, 8, 9, 10, and 12 arecomposite, but 1, 2, 3, 5, 7, and 11 are not.

In other words, a composite numberis a non-prime other than one or zero.Let C = {100, 110, 1000, 1001, 1010, ... ,1011011, ... } be the set of all binary representations of composite numbers. To design an "efficient" algorithmdeciding C is an ancient, important, and difficult problem. To design such analgorithm it would seem necessary to come up with a clever way of discoveringthe factors, if any, of a number ~a task that seems quite complex.

Naturally,by searching exhaustively all numbers smaller than the given number (in fact,smaller than its square root) we would end up discovering its factors; the pointis that no more direct method is evident.However, if nondeterminism is available, we can design a machine to semidecide C rather simply, by guessing the factors, if there are any.

This machineoperates as follows, when given as input the binary representation of integer n:(1) Nondeterministically choose two binary numbers p, q larger than one, bitby bit, and write their binary representation next to the input.(2) Use the multiplication machine of Problem 4.3.5 (actually, the single-tapemachine that simulates it) to replace the binary representations of p and qby that of their product.(3) Check to see that the two integers, n and p . q, are the same. This can bedone easily by by comparing them bit by bit. Halt if the two integers areequal; otherwise continue forever in some fashion (recall that at present weare only interested in a machine that semidecides C).224Chapter 4: TURING MACHINESThis machine, on input 1000010 (the binary representation of 66) willhave many rejecting (nonhalting) computations, corresponding to phase 1 abovechoosing pairs of binary integers, such as 101; 11101, that fail to multiply to 66.The point is that, since 66 is a composite number, there will be at least one computation of M that will end up accepting -and that is all we need.

In fact, therewill be more than one (corresponding to 2 . 33 = 6 . 11 = 11 . 6 = 33 . 2 = 66).If the input were 1000011, however, no computation would end up accepting-because 67 is a prime number.This machine can be modified to a nondeterministic machine that decidesthe language C. The deciding machine has the same basic structure, except thatin Phase (1) the new machine never guesses an integer with more bits than nitself -obviously, such an integer cannot be a factor of n. And in Phase 3, aftercomparing the input and the product, the new machine would halt at state yif they are equal, and at state n otherwise. As a result, all computations willeventually halt after some finite number of steps.The upper bound N required by Definition 4.5.2 is now easy to computeexplicitly.

Suppose that the given integer n has £ bits. Let N, be the maximumnumber of steps in any computation by the multiplying machine on any input oflength 2£+ 1 or less; this is a finite number, the maximum of finitely many naturalnumbers. Let N2 the number of steps it takes to compare two strings of lengthat most 3£ each.

Then any computation by M' will halt after Nl + N2 + 3£ + 6steps, certainly a finite number depending only on the machine and the input.ONondeterminism would seem to be a very powerful feature that cannot beeliminated easily. Indeed, there appears to be no easy way to simulate a nondeterministic Turing machine by a deterministic one in a step-by-step manner,as we have done in all other cases of enhanced Turing machines that we haveexamined so far. However, the languages semidecided or decided by nondeterministic Turing machines are in fact no different from those semidecided ordecided, respectively, by deterministic Turing machines.Theorem 4.5.1: If a nondeterministic Turing machine M semidecides or decides a language, or computes a function, then there is a standard Turing machine Af' semi deciding or deciding the same language, or computing the samefunction.Proof: We shall describe the construction for the case in which M semidecidesa language L; the constructions for the case of deciding a language or computinga function are very similar.

So, let M = (K,~,~, s, H) be a nondeterministicTuring machine semideciding a language L. Given an input 'W, M' will attemptto run systematically through all possible computations by M, searching for onethat halts. When and if it discovers a halting computation, it too will halt.

SoM' will halt if and only if M halts, as required.4.5: Nondeterministic Turing Machines225But M may have an infinity of different computations starting from thesame input; how can M explore them all? It does so by using a dovetailingprocedure (recall the argument illustrated in Figure 1-8).

The crucial observationis the following: Although for any configuration C of M there may be severalconfigurations C' such that C f- C', the number of such configurations C' isfixed and bounded in a way that depends only on M, not on C. Specifically,the number of quadruples (q, a,p, b) E ~ that can be applicable at any point isfinite; in fact, it cannot exceed IKI· (I~I + 2), since this is the maximum numberof possible combinations (p, b) with p E K and b E ~ U {t-, --t}.

Let us call rthe maximum number of quadruples that can be applicable at any point; thenumber r can be determined by inspection of M. In fact, we shall assume thatfor each state-symbol combination (q, a), and for each integer i E {I, 2, ... , r},there is a well-defined ith applicable quadruple (q,a,pi,b i ). If for some statesymbol combination (q, a) there are fewer than r relevant quadruples in ~, thensome may be repeated.Since M is nondeterministic, it has no definite way to decide at each stephow to choose among its r available "choices." But suppose that we help itdecide.

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

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