1610906232-7ba7dbaea13262b50a6029d682cb7f1b (824370), страница 42
Текст из файла (страница 42)
,~, 0) onit -this will represent the left end of the k tapes. Go one square to theright and write the symbol (u, 1, U, 1, ... , U, 1) -this signifies that the firstsquares of all k tapes contain a U, and are all scanned by the heads. Proceed to the right. At each square, if a symbol a ¥- U is encountered, writein its position the symbol (a, 0, U, 0, ... , U, 0). If a U is encountered, thefirst phase is over. The tape contents of M' faithfully represent the initialconfiguration of M.(2) Simulate the computation by M, until M would halt (if it would halt).
Tosimulate one step of the computation of M, M' will have to perform thefollowing sequence operations (we assume that it starts each step simulationwith its head scanning the first "true blank," that is, the first square of itstape that has not yet been subdivided into tracks):(a) Scan left down the tape, gathering information about the symbolsscanned by the k tape heads of M. After all scanned symbols havebeen identified (by the l's in the corresponding even tracks), return tothe leftmost true blank.
No writing on the tape occurs during this partof the operation of M', but when the head has returned to the rightend, the state of the finite control has changed to reflect the k-tuple ofsymbols from ~, in the k tracks at the marked head positions.(b) Scan left and then right down the tape to update the tracks in accordance with the move of M that is to be simulated. On each pair of4.3: Extensions of the Turing Machine207tracks, this involves either moving the head position marker one squareto the right or left, or rewriting the symbol from ~.(3) When M would halt, M' first converts its tape from tracks into singlesymbol format, ignoring all tracks except for the first; it positions its headwhere M w~)Uld have placed its first head, and finally it halts in the samestate as M would have halted.l1any details have been omitted from this description.
Phase 2, while byno means conceptually difficult, is rather messy to specify explicitly, and indeedthere are several choices as to how the operations described might actually becarried out. One detail is perhaps worth describing. Occasionally, for some n >Iwl, M may have to move one of its heads to the nth square of the correspondingtape for the first time.
To simulate this, M' will have to extend the part of itstape that is divided into 2k tracks, and rewrite the first u to the right as the2k-tuple (W, 0, u, 0, ... , U, 0) E ~'.It is clear that M' can simulate the behavior of M as indicated in thestatement of the theorem. It remains to argue that the number of steps requiredby M' for simulating t steps of M on input x is O(t . (Ixl + t)).
Phase 1 ofthe simulation requires O(lxi) steps of M'. Then, for each step of M, M' mustcarry out the maneuver in Phase 2, (a) and (b). This requires M' to scan the2k-track part of its tape twice; that is, it requires a number of steps by M' thatis proportional to the length of the 2k-track part of the tape of M'. The questionis, how long can this part of M"s tape be'? It starts by being Ixl + 2 long, andsubsequently it increases in length by no more than one for each simulated stepof M. Thus, if t steps of M are simulated on input x, the length of the 2k-trackpart of the tape of M' is at most Ixl + 2 + t, and hence each step of M can besimulated by O(lxl + t) steps of M', as was to be shown .•By using the conventions described for the input and output of a k-tapeTuring machine, the following result is easily derived from the previous theorem.Corollary:Any function that is computed or language that is decided orsemidecided by a k-tape Turing machine is also computed, decided, or semidecided, respectively, by a standard Turing machine.Two-way Infinite TapeSuppose now that our machine has a tape that is infinite in both directions.
Allsquares are initially blank, except for those containing the input; the head isinitially to the left of the input, say. Also, our convention with the t> symbolwould be unnecessary and meaningless for such machines.It is not hard to see that, like multiple tapes, two-way infinite tapes do notadd substantial power to Thring machines. A two-way infinite tape can be easilysimulated by a 2-tape machine: one tape always contains the part of the tape to208Chapter 4: TURING MACHINESthe right of the square containing the first input symbol, and the other containsthe part of the tape to the left of this in reverse.
In turn, this 2-tape machinecan be simulated by a standard Thring machine. In fact, the simulation needonly take linear, instead of quadratic, time, since at each step only one of thetracks is active. Needless to say, machines with several two-way infinite tapescould also simulated in the same way.Multiple HeadsWhat if we allow a Thring machine to have one tape, but several heads onit? In one step, the heads all sense the scanned symbols and move or writeindependently. (Some convention must be adopted about what happens whentwo heads that happen to be scanning the same tape square attempt to writedifferent symbols.
Perhaps the head with the lower number wins out. Also, letus assume that the heads cannot sense each other's presence in the same tapesquare, except perhaps indirectly, through unsuccessful writes.)It is not hard to see that a simulation like the one we used for k-tapemachines can be carried out for Turing machines with several heads On a tape.The basic idea is again to divide the tape into tracks, all but one of which areused solely to record the head positions. To simulate one computational stepby the multiple-head machine, the tape must be scanned twice: once to findthe symbols at the head positions, and again to change those symbols or movethe heads as appropriate.
The number of steps needed is again quadratic, as inTheorem 4.3.1.The use of multiple heads, like multiple tapes, can sometimes drasticallysimplify the construction of a Thring machine. A 2-head version of the copyingmachine C in Examph~ 4.1.8 could function in a way that is much more naturalthan the one-head version (or even the two-tape version, Example 4.3.1); seeProblem 4.3.3.Two-Dimensional TapeAnother kind of generalization of the Thring machine would allow its "tape" tobe an infinite two-dimensional grid. (One might even allow a space of higherdimension.) Such a device could be much more useful than standard Turingmachines to solve problems such as "zigsaw puzzles" (see the tiling problem inthe next chapter).
We leave it as an exercise (Problem 4.3.6) to define in detailthe operation of such machines. Once again, however, no fundamental increasein power results. Interestingly, the number of steps needed to simulate t steps ofthe two-dimensional Thring machine on input x by the ordinary Turing machineis again polynomial in t and Ixl.The above extensions on the Thring machine model can be combined: Onecan think of Thring machines with several tapes, all or some of which are two-wayinfinite and have more than one head on them, or are even multidimensional.4.4: Random Access Turing Machines209Again, it is quite straightforward to see that the ultimate capabilities of theTuring machine remain the same.We summarize our discussion of the several variants of Turing machinesdiscussed so far as follows.Theorem 4.3.2: Any language decided or semidecided, and any function computed by Turing machines with several tapes, heads, two-way infinite tapes, ormulti-dimensional tapes, can be decided, semidecided, or computed, respectively,by a standard Turing machine.Problems for Section 4.34.3.1.
Formally define:(a) M semidecides L, where M is a two-way infinite tape Thring machine;(b) M computes f, where M is a k-tape Turing machine and f is a functionfrom strings to strings.4.3.2.(a)(b)(c)Formally define:a k-head Turing machine (with a single one-way infinite tape);a configuration of such a machine;the yields in one step relation between configurations of such a machine.(There is more than one correct set of definitions.)4.3.3. Describe (in an extension of our notation for k-tape Turing machines) a2-head Turing machine that compute the function f(w) = ww.4.3.4.
The stack of a pushdown automaton can be considered as a tape that can bewritten and erased only at the right end; in this sense a Turing machine isa generalization of the deterministic pushdown automaton. In this problemwe consider a generalization in another direction, namely the deterministicpushdown automaton with two stacks.(a) Define informally but carefully the operation of such a machine.
Definewhat it means for such a machine to decide a language.(b) Show that the class of languages decided by such machines is precisely theclass of recursive languages.4.3.5. Give a three-tape Turing machine which, when started with two binaryintegers separated by a ';' on its first tape, computes their product. (Hint:Use the adding machine of Example 4.3.2 as a "subroutine."4.3.6.
:Formally define a Turing machine with a 2-dimensional tape, its configurations, and its computation. Define what it means for such a machine todecide a language L. Show that t steps of this machine, starting on an inputof length n, can be simulated by a standard Turing machine in time that ispolynomial in t and n.210BChapter 4: TURING MACHINESRANDOM ACCESS TURING MACHINESDespite the apparent power and versatility of the variants of the Turing machines we have discussed so far, they all have a quite limiting common feature:Their memory is sequential; that is, in order to access the information stored atsome location, the machine must first access, one by one, all locations betweenthe current and the desired one.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
