1610906232-7ba7dbaea13262b50a6029d682cb7f1b (824370), страница 44

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 44)

Then Register 2 is doubled by instructions 71'13 through71'15, enforcing Invariant (a), and finally Register 3 is transferred to Register 1,enforcing (c). The iteration is then repeated. If at some point it is seen thatly /2 k - 1 J = 0, then the process terminates, and the final result is loaded fromRegister 4 to the accumulator.We can abbreviate this program as "mply 1," that is, an instruction withsemantics Ro := Ro . R 1 . We shall therefore feel free to use the instruction "mplyj" or "mply = e" in our programs, knowing that we can simulate them by theabove program. Naturally, the instruction numbers would be different, reflectingthe program of which this mply instruction is a part.

If a random access Turingmachine uses this instruction, then it is implicitly assumed that, in addition toits registers explicitly mentioned, it must have three more registers that play therole of Registers 2, 3, and 4 in the above program.OIn fact, we can avoid the cumbersome appearance of random access Turingmachine programs such as the one in the previous example by adopting someuseful abbreviations. For example, denoting the value stored in Register 1 byR 1 , in Register 2 by R 2 , and so on, we can writeas an abbreviation of the sequence1.2.3.4.load 1add 2sub =1store 14.4: Random Access Turing Machines215Once we adopt this, we could use better-looking names for the quantities storedat Registers 1 and 2, and express this sequence of instructions simply asx:= y+x -1.Here x and yare just names for the contents of Registers 1 and 2.

We can evenuse abbreviations likewhile x > 0 do x := x - 3,where x denotes the value of Register 1, instead of the sequence1.2.3.4.5.load 1jzero 6sub =3store 1jump 1Example 4.4.1 (continued): Here is a much more readable abbreviation ofthe mply program in Figure 4-20, where we are assuming that x and yare to bemultiplied, and the result is w:w:= 0while y > 0 dobeginz := half(y)if y - z - z =f. 0 then w := wx:= x+x+xy:= zendhaltThe correspondence between the form above and the original program inFigure 4-20 is this: y stands for R 1 , x for R 2 , z for R 3 , and w for R 4 • Noticethat we have also omitted for clarity the explicit instruction numbers; if gotoinstructions were necessary, we could label instructions by symbolic instructionlabels like a and b wherever necessary.Naturally, it is quite mechanical from an abbreviated program such as theabove to arrive to an equivalent full-fledged random access Turing machine program such as the original one.<)Although we have explained the mechanics of random access Turing machines, we have not said how they receive their input and return their output.In order to facilitate comparisons with the standard Turing machine model, weshall assume that the input-output conventions of random access Turing machines are very much in the spirit of the input-output conventions for ordinaryChapter 4: TURING MACHINES216Turing machines: The input is presented as a sequence of symbols in the tape.That is, although the tape of a random access Turin1!; machine may containarbitrary natural numbers, we assume that initially these numbers encode thesymbols of some input string.Definition 4.4.2: Let us fix an alphabet ~ ~the alphabet from which ourrandom access Turing machines will obtain their input~ with u E ~ and t> ~ ~(t> is not needed here, since a random access Turing machine is in no danger offallin1!; off the left end of its tape).

Also let E be a fixed bijection between ~ and{O, 1, ... , I~I - II}; this is how we encode the input and the output of randomaccess Turing machines. We assume that E(U) = O. The initial configurationof a random access Turing machine M = (k, II) with input w = ala2 ... an E(~- {U})* is (K,Ro, ... ,RHT), where K = 1, R j = 0 for all j, and T ={(I, E(ad), (2, E(a2)), ... , (n, E(a n ))).We say that M accepts string x E ~* if the initial configuration with inputx yields a halted configuration with Ro = 1.

We say it rejects x if the initialconfi1!;uration with input x yields a halted configuration with Ro = O. In otherwords, once M halts, we read its verdict at Register 0; if this value is 1, themachine accepts, if it is 0, it rejects.Let :Eo <;;; :E - {U} be an alphabet, and let L <;;; ~~ be a language.

We saythat M decides L if whenever x E L, M accepts x, and whenever x ~ L Mrejects x. We say that M semi decides L if the following is true: x E L if andonly if M on input x yields some halted configuration.Finally, let f :H ~o be a function.

We say that "U computes f if, forall x E ~o, the starting configuration of machine M with input x yields a haltedconfi1!;uration with these tape contents: {(1,E(ad), (2,E(a2)), ... , (n,E(a n ))),where f(x) = al ... an·:EoExample 4.4.2: We describe below a random access Turing machine program,in abbreviated form, deciding the language {anbnc n : n 2: O}.aeount := bcount := ccount := 0, n := 1while T[nJ = 1 do: n := n + 1, aeount := acount + 1while T[nJ = 2 do: n := n + 1, beount := bcount + 1while T[nJ = 3 do n := n + 1, aeount := acount + 1if acount = bcount = ccount and T[nJ = 0 then accept else rejectWe are assuming here that E(a) = 1, E(b) = 2, E(c) = 3, and we are usingthe variables aeount, bcount, and ceount to stand for the number of a's, b's,and e's, respectively, found so far.

We are also using the abbreviation accept for"load =1, halt" and reject for "load =0, halt." <)Example 4.4.3: For a more substantial example, we now describe a randomaccess Turing machine that computes the reflexive transitive closure of a finite4.4: Random Access Turing Machines217binary relation (recall Section 1.6).

We are given a directed graph R <;;; A x A,where A = {ao, ... ,an-d, and we wish to compute R*.One important question immediately arises: Row are we to represent arelation R <;;; A x A as a string? R can be represented in terms of its adjacencymatrix A R , an n x n matrix with 0-1 entries such that the i,jth entry is 1 ifand only if (ai, aj) E R (see Figure 4-21 for an example). In turn, the adjacencymatrix can be represented as a string in {O, 1}* of length n 2 , by first arrangingthe first row of the matrix, then the second row, and so on.

We denote the stringrepresentation of the adjacency matrix of a relation R as XR. For example, if Ris the binary relation shown in Figure 4-21(a), then AR and XR are as shown inFigure 4-21(b) and (c), respectively.0101011000011000(c)Figure 4-21: A graph, its adjacency matrix, and its string representation.We must therefore design a random access Turing machine M that computes the function f defined as follows: For any relation R over some finite set{aI, ...

, an}, f (X R) = x R*· Notice that we are not interested in how M respondsto inputs that are not in {O, 1 }n2, that is, inputs that do not represent adjacencymatrices of directed graphs.The program of M is shown below; we are assuming that E(O) = 1 andE(l) = 2. As always, E(U) = O.The first three instructions compute the number n of elements of the set A(one less than the smallest number whose square is the address of a blank in theinput tape).

From then on, the (i,j)th entry of the matrix, with 0 ~ i,j < n,can be fetched as the (i· n + j)-th symbol on the tape of II,I. Since this programis a straightforward implementation of the O(n 3 ) algorithm in Section 1.6, itis clear that it indeed computes the reflexive transitive closure of the relationrepresented by its input. Naturally, an unabbreviated random access Turingmachine program can be mechanically derived from the program above.OEvidently, the random access Turing machine is a remarkably powerful and218Chapter 4: TURING MACHINESn:= 1while T[n . n] -::f 0 do n := n + 1n:= n-1i:= 0while i < n do i := i + 1, T[i . n + i] := 2i:= j := k:= 0while j < n do j := j + 1,while i < n do i := i + 1,while k < n do k:= k + 1,if T[i .

n + j] = 2 and T[j . n + k] = 2 then T[i . nhalt+ k]:= 2agile model. How does its power compare to that of the standard Turing machine? It is very easy to see, and not at all surprising, that the random accessTuring machine is at least as powerful as the standard Turing machine. LetM = (K,~, 8, s, H) be a 1\lring machine; we can design a random access Turingmachine M' that simulates M. M' has a register, call it n, that keeps track ofthe head position of M On its tape. Initially n points to the beginning of the input.

Each state q E K is simulated by a sequence of instructions in the programof M'. For example, suppose that ~ = {U, a, b}, E(a) = 1, E(b) = 2, and let qbe a state of M such that 8(q, U) = (p, -+), 8(q, a) = (p, +---), 8(q, b) = (r, U), and8 (q, c» = (s, -+ ). The sequence of instructions simulating state q is this:q:if T[n] = 0 then n := n + 1, goto pif T[n] = 1 then if n > 0 then n := n - 1, goto pelse goto sif T[n] = 2 then T[n] := 0, goto rThe else clause in the third line (which should be present in any line simulating a +--- move) has the effect of the c> symbol, making sure that the headnever falls off the left end of M"s tape. We have shown:Theorem 4.4.1: Any recursive or recursively enumerable language, and anyrecursive function, can be decided, semi decided, and computed, respectively, bya random access Turing machine.The remarkable direction is the opposite:Theorem 4.4.2: Any language decided or semidecided by a random access Turing machine, and any function computable by a random access Turing machine,can be decided, semidecided, and computed, respectively, by a standard Turingmachine.

Характеристики

Список файлов решённой задачи