1610906232-7ba7dbaea13262b50a6029d682cb7f1b (824370), страница 39
Текст из файла (страница 39)
Let M = (K, 1:, J, s, {h}), whereK ={qo,ql,h},1: ={a,b,U,I>},s =qo,and J is given by the following table.q,qoqoqoqoqIqIqIqIuJ(q, u)ab(qI, b)(qI, a)(h,u)(qo, -+)(qo, -+)(qo, -+)(qO, -+)(qI, -+)UI>abUI>(a) Trace the computation of M starting from the configuration (qo,I>Qabbba).(b) Describe informally what M does when started in qo on any square of atape.4.1.2. Repeat Problem 4.1.1 for the machine M = (K, 1:, J, s, {h}), whereK ={ qo, qI, q2, h},1: ={a,b,U,I>},s =qo,and J is given by the following table (the transitions on I> are J (q, 1» = (q, I> ),and are omitted).q,qoqoqoqIqIqIq2q2q2(JJ(q, u)ab(qI, t-)(qo, -+)(qo, -+)(qI, t-)(q2,-+)(qI, t-)(q2,-+)(q2,-+)(h,U)UabUabUChapter 4: TURING MACHINES192Start from the configuration (qo, r>al!.b U bb U U U abn).4.1.3.
Repeat Problem 4.1.1 for the machine M = (K, 1:,15, s, {h}), whereK ={qO,ql,q2,q3,q4,h},1: ={a,b,U,r>},and 15 is given by the following table.q,qoqoqoqoqiqiqiqiq2q2q2q2q3q3q3q3q4q4q4q4uJ(q, u)abUr>abUr>abUr>abUr>abUr>(q2, -t)(q3, a)(h,U)(qo, -t)(q2, -t)(q2, -t)(q2, -t)(ql, -t)(qi , b)(q3, a)(h,U)(q2, -t)(q4,-t)(q4, -t)(q4, -t)(q3, -t)(q2, -t)(q4, -t)(h,u)(q4, -t)Start from the configuration (qo, r>gaabbbaa).4.1.4. Let M be the Turing machine (K, 1:,15, s, {h}), whereK ={qO,ql,q2,h},1: ={a,U,r>},and 15 is given by the following table.Let n 2: O.
Describe carefully what M does when started in the configuration (qo, r> U ang).1934.1: The definition of a Turing Machineq,fJofJofJofJifJifJi([2([2fJ2uJ(q, u)aU(qi, +-)(qo,U)(qo, --+)(q2, U)(h,U)(qi, --+ )(q2, a)(qo, +-)(q2, --+)I>aUI>aUI>4.1.5. In the definition of a Turing machine, we allow rewriting a tape squarewithout moving the head and moving the head left or right without rewritingthe tape square. What would happen if we also allowed to leave the headstationary without rewriting the tape square?4.1.6. (a) Which of the following could be configurations?(i) (q, I>a U aU, U, Ua)(ii) (q, abc, b, abc)(iii) (p, I>abc, a, e)(iv) (h,l>,e,e)(v) (q, I>a U ab, b, UaaU)(vi) (p, I>a, ab, Ua)(vii) (q, 1>, e, Uaa)(viii) (h, I>a, a, U U U U U U a)(b) Rewrite those of Parts (i) through (viii) that are configurations using theabbreviated notation.(c) Rewrite these abbreviated configurations in full.(i) (q,l>a!!.cd)(ii) (q,I>Q)(iii) (p, I>aa U U)(iv) (h, I>Uabc)4.1.
7. Design and write out in full a Turing machine that scans to the right untilit finds two consecutive a's and then halts. The alphabet of the Turingmachine should be {a, b, U, I> }.4.1.8. Give the full details of the Turing machines illustrated.>LL.194Chapter 4: TURING MACHINES4.1.9. Do the machines LR and RL always accomplish the same thing? Explain.4.1.10. Explain what this machine does.4.1.11. Trace the operation of the Thring machine of Example 4.1.8 when startedon I>Uaabb.4.1.12.
Trace the operation of the Thring machine of Example 4.1.9 on I> U aabbU.BCOMPUTING WITH TURING MACHINESWe introduced Turing machines with the promise that they outperform, as language acceptors, all other kinds of automata we introduced in previous chapters.So far, however, we have presented only the "mechanics" of Thring machines,without any indication of how they are to be used in order to perform computational tasks -to recognize languages, for example. It is as though a computerhad been delivered to you without a keyboard, disk drive, or screen -that is,without the means for getting information into and out of it.
It is time, therefore,to fix some conventions for the use of Turing machines.First, we adopt the following policy for presenting input to Turing machines:The input string, with no blank symbols in it, is written to the right of theleftmost symbol 1>, with a blank to its left, and blanks to its right; the head ispositioned at the tape square containing the blank between the I> and the input;and the machine starts operating in its initial state.
If M = (K,~, 15, s, H) is aThring machine and w E (~ - {U, I>})*, then the initial configuration of Mon input w is (s,I>Uw). With this convention, we can now define how Thringmachines are used as language recognizers.Definition 4.2.1: Let M = (K,~, 15, s, H) be a Thring machine, such that H ={y, n} consists of two distinguished halting states (y and n for "yes" and "no").Any halting configuration whose state component is y is called an acceptingconfiguration, while a halting configuration whose state component is n iscalled a rejecting configuration.
We say that M accepts an input w E(~- {U, I> }) * if (s, I>Uw) yields an accepting configuration; we say that M rejectsw if (s,I>Uw) yields a rejecting configuration.Let ~o ~ ~ - {U, I>} be an alphabet, called the input alphabet of M; byfixing ~o to be a subset of ~ - {U, I>}, we allow our Thring machines to use extrasymbols during their computation, besides those appearing in their inputs.
We4.2: Computing with Turing Machines195say that M decides a language L ~ I:~ if for any string 111 E I:~ the following istrue: If 111 E L then M accepts 111; and if w ~ L then M rejects 111.Finally, call a language L recursive if there is a TUring machine that decidesit.That is, a Turing machine decides a language L if, when started with inputit always halts, and does so in a halt state that is the correct response to theinput: y if w E L, n if w ~ L. Notice that no guarantees are given about whathappens if the input to the machine contains blanks or the left end symbol.Example 4.2.1: Consider the language L = {anbnc n : n 2: O}, which has111,heretofore evaded all types of language recognizers. The Turing machine whosediagram is shown in Figure 4-11 decides L.
In this diagram we have also utilizedtwo new basic machines, useful for deciding languages: Machine y makes thenew state to be the accepting state y, while machine n moves the state to n.ynFigure 4-11The strategy employed by M is simple: On input anbnc n it will operate inn stages. In each stage M starts from the left end of the string and moves tothe right in search of an a.
When it finds an a, it replaces it by a d and thenlooks further to the right for a b. When a b is found, it is replaced by a d, andthe machine then looks for a c. When a c is found and is replaced by a d, thenthe stage is over, and the head returns to the left end of the input. Then thenext stage begins. That is, at each stage the machine replaces an a, a b, and ac by d's. If at any point the machine senses that the string is not in a*b*c', orthat there is an excess of a certain symbol (for example, if it sees a b or c whilelooking for an a), then it enters state n and rejects immediately. If however itencounters the right end of the input while looking for an a, this means that allthe input has been replaced by d's, and hence it was indeed of the form anbnc n ,for some n 2: O.
The machine then accepts.OThere is a subtle point in relation to TUring machines that decide languages:With the other language recognizers that we have seen so far in this book (eventhe nondeterministic ones), one of two things could happen: either the machineaccepts the input, or it rejects it. A Turing machine, on the other hand, even if196Chapter 4: TURING MACHINESit has only two halt states y and n, always has the option of evading an answer("yes" or "no"), by failing to halt. Given a Turing machine, it might or it mightnot decide a language -and there is no obvious way to tell whether it does.The far-reaching importance -and necessity- of this deficiency will becomeapparent later in this chapter, and in the next.Recursive FunctionsSince Turing machines can write on their tapes, they can provide more elaborateoutput than just a "yes" or a "no:"Definition 4.2.2: Let M = (K, I:, 15, s, {h}) be a Turing machine, let I:o ~I: - {u, I>} be an alphabet, and let w E I:~.
Suppose that M halts on input w,and that (s,l>lJw) f-M (h,I>Uy) for some y E I:~. Then y is called the outputof M on input w, and is denoted M(w). Notice that M(w) is defined only ifM halts on input w, and in fact does so at a configuration of the form (h,I>Uy)with y E I:~.Now let f be any function from I:o to I: o. We say that M computesfunction f if, for all w E I: o, M(w) = f(111).
That is, for all w E I:~ Meventually halts on input w, and when it does halt, its tape contains the stringI> U f (w). A function f is called recursive, if there is a Turing machine M thatcomputes f.Example 4.2.2: The function 1'0, : I:* r--+ I:* defined as K,(w) = ww can becomputed by the machine C S+--, that is, the copying machine followed by theleft-shifting machine (both were defined towards the end of the last section). 0Strings in {O, 1}* can be used to represent the nonnegative integers in thefamiliar binary notation. Any string w = ala2 ... an E {0,1}* represents thenumbernum (w ) = al .
2n-l + a2 . 2n-2 + ... + anAnd any natural number can be represented in a unique way by a string inU 1(0 U 1)* -that is to say, without redundant O's in the beginning.Accordingly, Turing machines computing functions from {O, 1}* to {O, 1}*can be thought of as computing functions from the natural numbers to thenatural numbers.
In fact, numerical functions with many arguments -such asaddition and multiplication- can be computed by Turing machines computingfunctions from {O, 1,;}* to {O, 1}*, where ";" is a symbol used to separate binaryarguments.°Definition 4.2.3: Let M = (K, I:, 15, s, {h}) be a Turing machine such that0,1,; E I:, and let f be any function from N k to N for some k 2' 1. We say1974.2: Computing with Turing Machines°that M computes function J if for all WI,' ..
,Wk E U 1{O, 1}' (that is, forany k strings that are binary encodings of integers), num(M(wI; ... ;Wk)) =J(num(wt}, ... , num(wk)). That is, if M is started with the binary representations of the integers nl, ... ,nk as input, then it eventually halts, and when itdoes halt, its tape contains a string that represents number J(nl' ... ,nd -thevalue of the function.
A function J : Nk H N is called recursive if there is aTuring machine M that computes J.In fact, the term recursive used to describe both functions and languagescomputed by Turing machines originates in the study of such numerical functions. It anticipates a result we shall prove towards the end of this chapter,namely that the numerical functions computable by Turing machines coincidewith those that can be defined recursively from certain basic functions.Example 4.2.3: We can design a machine that computes the successor functionsucc(n) = n + 1 (Figure 4.12; SR is the right-shifting machine, the rightwardanalog of the machine in Example 4.1. 9). This machine first finds the right endof the input, and then goes to the left as long as it sees 1's, changing all of themto O's. When it sees a 0, it changes it into a 1 and halts.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
