1610906232-7ba7dbaea13262b50a6029d682cb7f1b (824370), страница 41
Текст из файла (страница 41)
A k-tape Turing machine is aquintuple (K,~, 5, s, H), where K, ~, s, and H are as in the definition of theordinary Turing machine, and 5, the transition function, is a function from(K - H) x ~k to K x (~U {+-, -+})k. That is, for each state q, and each k-tupleof tape symbols (al, ...
,ak), 5(q,(al, ... ,ak)) = (p,(bl, ... ,b k )), wherep is, asbefore, the new state, and bj is, intuitively, the action taken by M at tape j.Naturally, we again insist that if aj = ~ for some j ~ k, then bj =-+.Computation takes place in all k tapes of a k-tape Turing machine.
Accordingly, a configuration of such a machine must include information about alltapes:Definition 4.3.2: Let M = (K,~, 5, s, H) be a k-tape Turing machine. Aconfiguration of M is a member ofKX(L>~'X(~'(~-{u})U{e}))k.That is, a configuration identifies the state, the tape contents, and the headposition in each of the k tapes.If (q, (WI al UI, ... , Wkakuk)) is a configuration of a k-tape Turing machine(where we have used the k-fold version of the abbreviated notation for configurations), and if 5(p,(al, ...
,ak)) = (bl, ... ,b k ), then in one move the machine202Chapter 4: TURING MACHINESITape 1iTape 2Tape kFinite controlhFigure 4-14would move to configuration (p, (w~ a~ u~ , ... , w~ a~ u~)), where, for i = 1, ... , k,w~a~u~ is WiaiUi modified by action bi , precisely as in Definition 4.1.3. WesaJthat configuration (q, (WI aIUI, ... ,Wkakuk)) yields in one step configurationIIIIII))( p, ( wIaIuI,···,wkakuk.Example 4.3.1: A k-tape Turing machine can be used for computing a functionor deciding or semi deciding a language in any of the ways discussed above forstandard Turing machines.
We adopt the convention that the input string isplaced on the first tape, in the same way as it would be presented to a standardTuring machine. The other tapes are initially blank, with the head on theleftmost blank square of each. At the end of a computation, a k-tape Turingmachine is to leave its output on its first tape; the contents of the other tapesare ignored.Multiple tapes often facilitate the construction of a Turing machine to perform a particular function. Consider, for example, the task of the copying machine C given in Example 4.1.8: to transform L> U wb[ into L> U w U wb[, wherew E {a, b}·. A 2-tape Turing machine can accomplish this as follows.(1)~1ovethe heads on both tapes to the right, copying each symbol on the first2034.3: Extensions of the Turing Machinetape onto the second tape, until a blank is found on the first tape.
The firstsquare of the second tape should be left blank.(2) Move the head on the second tape to the left until a blank is found.(3) Again move the heads on both tapes to the right, this time copying symbolsfrom the second tape onto the first tape. Halt when a blank is found on thesecond tape.This sequence of actions can be pictured as follows.At the beginning:After (1):After (2):After (3):First tapeSecond tapeFirst tapeSecond tapeFirst tapeSecond tapeFirst tapeSecond tapec>k!wc>k!L> U wk!c> U wl,!c> U wUc>l,!wc> U w U wUL> U wl,!Turing machines with more than one tape can be depicted in the same waythat single-tape Turing machines were depicted in earlier sections.
We simplyattach as a superscript to the symbol denoting each machine the number of thetape on which it is to operate; all other tapes are unaffected. For example, U 2writes a blank on the second tape, L~ searches to the left for a blank on the firsttape, and R 1 ,2 moves to the right the heads of both the first and the second tape.A label a 1 on an arrow denotes an action taken if the symbol scanned in thefirst tape is an a. And so on. (When representing multi-tape Turing machines,we refrain from using the shorthand M2 for MM.) Using this convention, the2-tape version of the copying machine might be illustrated as in Figure 4-15.
Weindicate the submachines performing Functions 1 through 3 above.OT(1)'-.,-J \.......-~T---'(2)(3)Figure 4-15Example 4.3.2: We have seen (Example 4.2.3) that Turing machines can add1 to any binary integer. It should come as no surprise that Turing machines204Chapter 4: TURING MACHINEScan also add arbitrary binary numbers (recall Problem 2.4.3, suggesting thateven finite automata, in a certain sense, can). With two tapes this task can beaccomplished by the machine depicted in Figure 4-16. Pairs of bits such as 01on an arrow label are a shorthand for, in this case, a 1 = 0, a 2 = 1.Figure 4-16This machine first copies the first binary integer in its second tape, writingzeros in its place (and in the place of the ";" separating the two integers) in thefirst tape; this way the first tape contains the second integer, with zeros addedin front.
The machine then performs binary addition by the "school method,"starting from the least significant bit of both integers, adding the correspondingbits, writing the result in the first tape, and "remembering the carry" in itsstate·OWhat is more, we can build a 3-tape Turing machine that multiplies twonumbers; its design is left as an exercise (Problem 4.3.5).Evidently, k-tape Turing machines are capable of quite complex computational tasks. We shall show next that any k-tape Turing machine can besimulated by a single-tape machine.
By this we mean that, given any k-tapeTuring machine, we can design a standard Turing machine that exhibits thesame input-output behavior -decides or semidecides the same language, computes the same function. Such simulations are important ingredients of ourmethodology in studying the power of computational devices in this and thenext chapters.
Typically, they amount to a method for mimicking a single stepof the simulated machine by several steps of the simulating machine. Our firstresult of this sort, and its proof, is quite indicative of this line of reasoning.4.3: Extensions of the Turing Machine205Theorem 4.3.1: Let M = (K, ~,b, s, H) be a k-tape Turing machine for somek :::: 1. Then there is a standard Thring machine M' = (K', ~', b', s', H), where~ ~ ~', and such that the following holds: For any input string x E ~', M oninput x halts with output y on the first tape if and only if M' on input x haltsat the same halting state, and with the same output y on its tape. Furthermore,if M halts on input x after t steps, then M' halts on input x after a number ofsteps which is O(t· (Ixl + t)).~Ia IUbaIUUt~IbbbtIiIu Iu Iu I i(a)~aUbauu0001000~bbbuuu0010000~uu~(b)Figure 4-17Proof: The tape of M' must somehow contain all information in all tapes of M.A simple way of achieving this is by thinking that the tape of M' is divided intoseveral tracks (see Figure 4-18(b)), with each "track" devoted to the simulationof a different tape of M.
In particular, except for the leftmost square, whichcontains as usual the left end symbol ~, and the infinite blank portion of thetape to the right, the single tape of M' is split horizontally into 2k tracks.The first, third, ... , (2k - l)st tracks of the tape of M' correspond to the first,second, ... ,kth tapes of lv!. The second, fourth, ... ,2kth tracks of the tape of206Chapter 4: TURING MACHINESM' are used to record the positions of the heads on the first, second, ... , kthtapes of M in the following way: If the head on the ith tape of M is positionedover the nth tape square, then the 2ith track of the tape of M' contains a 1 inthe (n + l)st tape square and a in all tape squares except the (n + l)st. Forexample, if k = 2, then the tapes and heads of M shown in Figure 4-18(a) wouldcorrespond to the tape of M' shown in Figure 4-18(b).Of course, the division of the tape of M' into tracks is a purely conceptualdevice; formally, the effect is achieved by letting°~'=~U(~x{O,l})k.That is, the alphabet of M' consists of the alphabet of M (this enables M' toreceive the same inputs as M and deliver the same output), plus all 2k-tuplesof the form (al,bl, ...
,ak,b k ) with al, ... ,ak E ~ and bl, ... ,bk E {0,1}. Thetranslation from this alphabet to the 2k-track interpretation is simple: We readany such 2k-tuple as saying that the first track of M' contains aI, the secondbl , and so on up to the 2kth track containing bk . This in turn means that thecorresponding symbol of the ith tape of M contains ai, and that this symbol isscanned by the ith head if and only if bi = 1 (recall Figure 4-17(b)).When given an input w E ~', M' operates as follows.(1) Shift the input one tape square to the right. Return to the square immediately to the right of the ~, and write the symbol (~, 0, L>, 0, ...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
