1610906232-7ba7dbaea13262b50a6029d682cb7f1b (824370), страница 43
Текст из файла (страница 43)
In contrast, real computers have random accessmemories, each element of which can be accessed in a single step, if appropriately addressed. What would happen if we equipped our machines with such arandom access capability, enabling them to access any desired tape square in asingle step? To attain such a capability, we must also equip our machines withregisters, capable of storing and manipulating the addresses of tape squares. Inthis subsection we define such an extension of the Turing machine; significantly,we see that it too is equivalent in power to the standard Turing machine, withonly a polynomial loss in efficiency.IR31IR21Registers[EDoProgram counterIT[ ll l T[2ll T[3ll T[4ll T[5ll· ..IRO IFigure 4-18A random access Turing machine has a fixed number of registers and a oneway infinite tape (see Figure 4-18; we continue to call the machine's memory a"tape" for compatibility and comparison with the standard model, despite thefact that, as we shall see, it behaves much more like a random access memorychip).
Each register and each tape square is capable of containing an arbitrary natural number. The machine acts on its tape squares and its registers asdictated by a fixed program -the analog of the transition function of ordinaryTuring machines. The program of a random access Turing machine is a sequenceof instructions, of a kind reminiscent of the instruction set of actual computers.The kinds of instructions allowed are enumerated in Figure 4-19.Initially the register values are 0, the program counter is 1, and the tapecontents encode the input string in a simple manner that will be specified shortly.Then the machine executes the first instruction of its program. This will changethe contents of the registers or of the tape contents as indicated in Figure 4-19;2114.4: Random Access Turing MachinesInstructionOperandSemanticsreadwritestoreloadloadaddaddsubsubhalfjumpjposjzerohaltjjjj=cj=cj=cRo:= T[Rj ]T[Rj ]:= RoR j := RoRo:= R jRo:= cRo:= Ro + R jRo:= Ro + cRo := ma.x{Ro - R j , O}Ro:= max{Ro - c,O}R0 .· - l B.o..) JK:= sif Ro > 0 then K := sif Ro = 0 then K := sK:= 0sssNotes: j stands for a register number, 0 ~ j < k.
T[i] denotes the current contentsof tape square i. Rj denotes the current contents of Register j. s ~ p denotes anyinstruction number in the program. c is any natural number. All instructions changeK to K + 1, unless explicitly stated otherwise.Figure 4-19also, the value of the program counter K, an integer identifying the instructionto be executed next, will be computed as indicated in the figure. Notice thespecial role of Register 0: it is the accumulator, where all arithmetic and logicalcomputation takes place.
The Kth instruction of the program will be executednext, and so on, until a halt instruction is executed --at this point the operationof the random access Turing machine ends.We are now ready to define formally a random access Turing machine, itsconfigurations, and its computation.Definition 4.4.1: A random access 'lUring machine is a pair AI = (k, ll),where k > 0 is the number of registers, and II = (1fl' 1f2, ...
,1fp), the program,is a finite sequence of instructions, where each instruction 1fi is of one of thetypes shown in Figure 4-19. We assume that the last instruction, 1fp, is alwaysa halt instruction (the program may contain other halt instructions as well).A configuration of a random access Turing machine (k, ll) is a k + 2-tuple(K, Ro, R 1 ,·· ., R k - 1 , T), whereKEN is the program counter, an integer between 0 and p. The configuration is a halted configuration if K is zero.For each j, 0 ~ j < k, R j EN is the current value of Register j.T, the tape contents, is a finite set of pairs of positive integers ~that is,Chapter 4: TURING MACHINES212a finite subset of (N - {O}) x (N - {O})- such that for all i 2: 1 there is atmost one pair of the form (i, m) E T.Intuitively, (i, m) E T means that the ith tape square currently containsthe integer m > O.
All tape squares not appearing as first components of a pairin T are assumed to contain O.Definition 4.4.1 (continued): Let M = (k,II) be a random access machine.We say that configuration C = ("', R o, Rl, ... , Rk-l, T) of M yields in one stepconfiguration C ' = (",I,R~, . ..
,Rk_1 , T'), denoted C I- M C ' , if, intuitively,the values of ",I, the Rj's and T' correctly reflect the application to "', the Rj's,and T of the "semantics" (as in Figure 4-19) of the current instruction IrK' Weshall indicate the precise definition for a only a few of the fourteen kinds ofinstructions in Figure 4-19.If IrK is of the form read j, where j < k, then the execution ofthis instructionhas the following effect: The value contained in Register 0 becomes equal tothe value stored in tape square number R j -the tape square "addressed" byRegister j.
That is, R~ = T[Rj], where T[Rj) is the unique value m such that(Rj,m) E T, if such an m exists, and 0 otherwise. Also, ",' = "'+ 1. All othercomponents of the configuration C ' are identical to those of C.If IrK is of the form add = c, where c 2: 0 is a fixed integer such as 5, thenwe have R~ = Ro + c, and ",' = '" + 1, with all other components remaining thesame.If IrK is of the form write j, where j < k, then we have ",' = '" + 1, T' is Twith any pair of the form (Rj, m), if one exists, deleted, and, if Ro > 0, the pair(Rj, Ro) added; all other components remain the same.If IrK is of the form jpos s, where 1 :::; s :::; p, then we have ",' = s if Ro > 0,and ",' = C + 1 otherwise; all other components remain the same.Similarly for the other kinds of instructions.
The relation yields, I-M' isthe reflexive transitive closure of I- M.m,Example 4.4.1: The instruction set of our random access Thring machine (recallFigure 4-19) has no multiplication instruction mply. As it happens, if we allowedthis instruction as a primitive, our random access Thring machine, although stillequivalent to the standard Thring machine, would be much more time-consumingto simulate (see Problem 4.4.4).The omission of the multiplication instruction is no great loss, however,because this instruction can be emulated by the program shown in Figure 420.
Ift Register 0 initially contains a natural number x and Register 1 initiallytThe computation of a random access Turing machine starts with all registers O.4.4: Random Access Turing Machines213°contains y, then this random access Thring machine will halt, and Register willcontain the product x· y. Multiplication is done by successive additions, wherethe instruction half is used to reveal the binary representation of y (actually, ourinstruction set contains this unusual instruction precisely for this use).l.2.3.4.5.6.7.8.9.10.11.12.13.14.15.16.17.19.18.19.20.store 2load 1jzero 19halfstore 3load 1sub 3sub 3jzero 13load 4add 2store 4load 2add 2store 2load 3store 1load 4jump 2load 4haltFigure 4-20Here is a typical sequence of configurations (since this machine does notinteract with tape squares, the T part of these configurations is empty; thereare k = 5 registers):(1;5,3,0,0,0;0) f-- (2;5,3,5,0,0;0) f-- (3;3,3,5,0,0;0) f-- (4;3,3,5,0,0;0) f-(5; 1,3,5,0,0; 0) f-- (6; 1,3,5,1,0; 0) f-- (7; 3, 3, 5,1,0; 0) f-- (8; 2,3,5,1,0; 0) f-(9; 1,3,5,1,0; 0) f-- (10; 1, 3, 5,1,0; 0) f-- (11; 0,3,5,1,0; 0) f-(12; 5, 3, 5, 1, 0; 0) f-- (13; 5,3,5,1,5; 0) f-- (14; 5, 3, 5,1,5; 0) f-(15; 10,3,5,1,5; 0) f-- (16; 10,3,10,1,5; 0) f-- (17; 1,3,10,1,5; 0) f-(18; 1, 1, 10, 1, 5; 0) f-- (2; 1, 1, 10, 1, 5; 0) f--* (18; 0, 0, 20, 0,15; 0) f-(2; 0, 0, 20, 0, 15; 0) f-- (3; 0, 0, 20, 0, 15; 0) f-- (19; 0, 0, 20, 0, 15; 0) f-(20;15,0,20,0,15;0) 1However, since the present program is intended to be used as a part of otherrandom access Turing machines, it makes sense to explore what would happen ifit were started at an arbitrary configuration.Chapter 4: TURING MACHINES214Let x and y be the nonnegative integers stored in Registers 0 and 1, respectively, at the beginning of the execution of this program.
We claim that themachine eventually halts with the product x· y stored in Register O-as if it hadexecuted the instruction "mply 1." The program proceeds in several iterations.An iteration is an execution of the sequence of instructions 71'2 through 71'18. Atthe kth iteration, k 2: 1, the following conditions hold:(a)(b)(c)(d)RegisterRegisterRegisterRegister2 contains x2k,3 contains ly /2k J,1 contains ly /2 k - 1 J,4 contains the "partial result" x· (y mod 2k).The iteration seeks to maintain these "invariants." So, instructions 71'2through 71'5 enforce Invariant (b), assuming (c) held in the previous iteration.Instructions 71'6 through 71'8 compute the kth least significant bit of y, and, if thisbit is not zero, instructions 71'9 through 71'12 add x2 k - 1 to Register 4, as mandated by Invariant (d).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
