1610906232-7ba7dbaea13262b50a6029d682cb7f1b (824370), страница 38
Текст из файла (страница 38)
Forthe three configurations illustrated in Figure 4-2, the tape contents would berepresented as C>Qaba, C> U U1J U a, and C> U a U 1J. Also, we can write configurationsby including the state together with the notation for the tape and head position.That is, we can write (q,wa,u) as (q,wQu). {)sing this convention, we wouldChapter 4: TURING MACHINES184~IIbaIaUU~I{IUUI I Ia IUtqh_q'~,a,q'q"q"(q,U\qhUaba)(h.[>UU, U,Ua)Ufqhtq'q"(q,~UaU, U, e)Figure 4-2write the three configurations shown in Figure 4-2 as (q, ~Qaba), (h, ~ U U!J U a),and (q,~UaU!J).Definition 4.1.3: Let M = (K,~, 0, s, H) be a Thring machine and considertwo configurations of M, (ql, wialud and (q2, W2a2u2), where al,a2 E ~. Then(ql, WI al UI) f- M (q2, W2 a2u :!)if and only if, for some b E~U {+-, -+}, O(ql, ad = (q2, b), and eitherUIi1854.1: The definition of a Turing Machine1.
b E ~, WI = W2, U1 = U2, and a2 = b, or2. b =f-, WI = W2a2, and either(a) U2 = a1U1, if a1 i: U or U1 i: e, or(b) U2 = e, if a1 = U and U1 = e: or3. b =-+, W2 = W1a1, and either(a) U1 = a2U2, or(b) U1 = U2 = e, and a2 = U.In Case 1, M rewrites a symbol without moving its head. In Case 2, Mmoves its head one square to the left; if it is moving to the left off blank tape,the blank symbol on the square just scanned disappears from the configuration.In Case 3, M moves its head one square to the right; if it is moving onto blanktape, a new blank symbol appears in the configuration as the new scannedsymbol. Notice that all configurations, except for the halted ones, yield exactlyone configuration.Example 4.1.3: To illustrate these cases, let w, U Ewith a U, and let a, b E ~.~*,whereUdoes not endCase 1.
J(q1,a) = (q2,b).Example: (q1,WqU) f-M (q2,WQU).Case 2. J(q1,a) = (q2,f-).Example for (a): (Q1, wbqu) f- M (Q2, w!2.au).Example for (b): (Q1,wbU) f-M (Q2,W!2.).Case 3. J(Q1, a) = (Q2, -+).Example for (a): (Q1,wqbu) f-M (Q2,waQu).Example for (b): (Q1, wq) f- M (Q2, wa1J). 0Definition 4.1.4: For any Thring machine M, let, f-'M be the reflexive, transitiveclosure of f- M; we say that configuration C 1 yields configuration C 2 if C1 f-'M C2 •A computation by M is a sequence of configurations Co, C 1 , ...
, Cn, for somen 2: 0 such thatWe say that the computation is of length n or that it has n steps, and we writeCO f-M Cn.Example 4.1.4: Consider the Thring machine M described in Example 4.1.1. IfM is started in configuration (Ql, C>Uaaaa), its computation would be represented186Chapter 4: TURING MACHINESformally as follows.(ql, c>!:!aaaa) f- M (qo, c> U Qaaa)f- M (ql , c> U !:!aaa)f- M (qo, c> U UQaa)f- M (qI, C> U U!:!aa)f- M(qO,C>f- M (qI, C> U Uf- M(qO,C>Qa)U !:!a)UUUU U U UQ)f- M (qI, C> U U U U!:!)f- M ( qo, C> U U U U U !:!)f-M(h,C>U U U U U!:!)The computation has ten steps.<>.A Notation for Turing MachinesThe TUring machines we have seen so far are extremely simple -at least whencompared to our stated ambitions in this chapter- and their tabular form isalready quite complex and hard to interpret.
Obviously, we need a notation forThring machines that is more graphic and transparent. For finite automata, weused in Chapter 2 a notation that involved states and arrows denoting transitions. We shall next adopt a similar notation for Thring machines. However, thethings joined by arrows will in this case be themselves Turing machines. In otherwords, we shall use a hierarchical notation, in which more and more complexmachines are built from simpler materials. To this end, we shall define a verysimple repertoire of basic machines, together with rules for combining machines.The Basic Machines.
We start from very humble beginnings: The symbol-writingmachines and the head-moving machines. Let us fix the alphabet ~ of ourmachines. For each a E ~ U { -+, +- } - {c>}, we define a Thring machine M a =({s,h},~,J,s,{h}), where for each b E ~ - {C>}, J(s,b) = (h,a). Naturally,J(s,c» is still always (s, -+). That is, the only thing this machine does is toperform action a -writing symbol a if a E ~, moving in the direction indicatedby a if a E {+-, -+}- and then to immediately halt. Naturally, there is a uniqueexception to this behavior: If the scanned symbol is a c>, then the machine willdutifully move to the right.Because the symbol-writing machines are used so often, we abbreviate theirnames and write simply a instead of Ma.
That is, if a E ~, then the a-writingmachine will be denoted simply as a. The head-moving machines Mf- and M-+will be abbreviated as L (for "left") and R (for "right").1874.1: The definition of a Turing MachineThe Rules for Combining Machines. Turing machines will be combined in a waysuggestive of the structure of a finite automaton. Individual machines are likethe states of a finite automaton, and the machines may be connected to eachother in the way that the states of a finite automaton are connected together.However, the connection from one machine to another is not pursued until thefirst machine halts; the other machine is then started from its initial state withthe tape and head position as they were left by the first machine.
So if M 1 ,M 2, and M3 are Turing machines, the machine displayed in Figure 4-3 operatesas follows: Start in the initial state of M 1 ; operate as Ml would operate untilMl would halt; then, if the currently scanned symbol is an a, initiate M2 andoperate as A-12 would operate; otherwise, if the currently scanned symbol is a b,then initiate A-13 and operate as M3 would operate.Ml~M2M3Figure 4-3It is straightforward to give an explicit definition of the combined Turingmachine from its constituents. Let us take the machine shown in Figure 4-3above. Suppose that the three Turing machines M 1 , M 2, and M3 are Ml =(Kl,~,(h,Sl,Hl)' M2 = (K2,~,J2,S2,H2)' and M3 = (K3,~,J3,S:3,H3). Weshall assume, as it will be most convenient in the context of combining machines,that the sets of states of all these machines are disjoint.
The combined machineshown in Figure 4-3 above would then be M = (K,~, 15, s, H), whereK=K 1 UK 2 uK3,= Sl,H=H2 UH3·For each u E ~ and q E K - H, J(q, u) is defined as follows:(a) If q E KJ - HI, then J(q, u) = 15 1 (q, u).(b) If q E K 2 - H 2, then 15 (q, u) = 152 (q, u) .(c) If q E K3 - H 3, then J(q, u) = J3(q, u).(d) Finally, if q E HI -the only case remaining- then J(q, u)u = a, J(q, u) = S3 if u = b, and J(q, u) E H otherwise.sS2ifAll the ingredients of our notation are now in place.
We shall be buildingmachines by combining the basic machines, and then we shall further combinethe combined machines to obtain more complex machines, and so on. We knowthat, if we wished, we could come up with a quintuple form of every machine wethus describe, by starting from the quintuples of the basic machines and carryingout the explicit construction exemplified above.Chapter 4: TURING MACHINES188Example 4.1.5: Figure 4-4(a) illustrates a machine consisting of two copies ofR.
The machine represented by this diagram moves its head right one square;then, if that square contains an a, or a b, or a 1>, or a U, it moves its head onesquare further to the right.a>R~R>Ra,b,U ,".R~(a)(b)Figure 4-4It will be convenient to represent this machine as in Figure 4-4(b). That is,an arrow labeled with several symbols is the same as several parallel arrows, onefor each symbol. If an arrow is labeled by all symbols in the alphabet 1: of themachines, then the labels can be omitted. Thus, if we know that 1: = {a, b, 1>, U},then we can display the machine above asR~R,where, by convention, the leftmost machine is always the initial one.
Sometimesan unlabeled arrow connecting two machines can be omitted entirely, by juxtaposing the representations of the two machines. Under this convention, theabove machine becomes simply RR, or even R2.<;Example 4.1.6: If a E 1: is any symbol, we can sometimes eliminate multiplearrows and labels by using Ii to mean "any symbol except a." Thus, the machineshown in Figure 4-5(a) scans its tape to the right until it finds a blank.
We shalldenote this most useful machine by Ru.;)af u>R(a)(b)Figure 4-5Another shorthand version of the same machine as in Figure 4-5 (a) is shownin Figure 4-5(b). Here a -I- U is read "any symbol a other than U." The advantageof this notation is that a may then be used elsewhere in the diagram as the nameof a machine. To illustrate, Figure 4-6 depicts a machine that scans to the right1894.1: The definition of a Turing MachineuA"f u>RJ~LaFigure 4-6(a) Ru(b) Lu(c) Ru(d)LuFigure 4-7until it finds a nonblank square, then copies the symbol in that square onto thesquare immediately to the left of where it was found.OExample 4.1.7: Machines to find marked or unmarked squares are illustratedin Figure 4-7.
They are the following.(a) R u , which finds the first blank square to the right of the currently scannedsquare.(b) L u , which finds the first blank square to the left of the currently scannedsquare.(c) Rrr , which finds the first nonblank square to the right of the currentlyscanned square.(d) L rr , which finds the first nonblank square to the left of the currently scannedsquare.OExample 4.1.8: The copying machine C performs the following function: If Cstarts with input w, that is, if string 'UJ, containing only nonblank symbols butpossibly empty, is put on an otherwise blank tape with one blank square to its190Chapter 4: TURING MACHINESleft, and the head is put on the blank square to the left of w, then the machinewill eventually stop with w U w on an otherwise blank tape.
We say that Ctransforms UwlJ into UwUwld.A diagram for C is given in Figure 4-8.0Figure 4-8Example 4.1.9: The right-shifting machine S-7' transforms UwlJ., where w contains no blanks, into UU w.1d· It is illustrated in Figure 4-9.0Figure 4-9Example 4.1.10: Figure 4-10 is the machine defined in Example 4.1.1, whicherases the a's in its tape.~>R~uFigure 4-10As a matter of fact, the fully developed transition table of this machinewill differ from that of the machine given in Example 4.1.1 in ways that aresubtle, inconsequential, and explored in Problem 4.1.8 -namely, the machinein Figure 4-10 will also contain certain extra states, which are final states of itsconstituents machines.O1914.1: The definition of a Turing MachineProblems for Section 4.14.1.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
