1610906232-7ba7dbaea13262b50a6029d682cb7f1b (824370), страница 45
Текст из файла (страница 45)
Furthermore, if the machines halt on an input, then the number ofsteps taken by the standard Turing machine is bounded by a polynomial in thenumber of steps of the random access Turing machine on the same input.4.4: Random Access Turing Machines219Proof: Let M = (k, II) be a random access Turing machine deciding or semideciding a language L ~ ~* or computing a function from ~* to ~*. We willoutliue the design an ordinary Turing machine M' that simulates M. We shalldescribe M' as a (k + 3)-tape machine, where k is the number ofregisters of M,which simulates M; we know from Theorem 4.3.1 that such a machine can inturn be simulated by the basic model.Turing machine M' keeps track of the current configuration of the randomaccess Turing machine M, and repeatedly computes the next configuration.
Thefirst tape is used only for reading the input of M, and possibly for reporting theoutput at the end, in the case where M computes a function. The second tape isused for keeping track of the T part of the configuration -the tape contents ofM.
The relation T is maintained as a sequence of strings of the form (111,10),a left parenthesis followed by the binary representation of an integer, followedby a comma, followed by another binary integer, followed by a right parenthesis.The intended meaning of the above string is that the seventh tape square ofM contains the integer 2.
The pairs of integers in the sequence representingT are not in any particular order, and may be separated by arbitrarily longsequences of blanks (this necessitates an endmarker, such as $, at the end of therepresentation of T, to help M' decide when it has seen all such pairs). Each ofthe next k tapes of M' maintain the contents of a register of M, also in binary.The current value of the program counter K of M is maintained in the state ofM' in a manner to be explained below.The simulation has three phases. During the first phase, M' receives onits first tape the input x = al a2 ...
an E ~*, and converts it to the string(1, E(ad) ... (n, E(a,,)) on the second tape. Thus M' can start the second phase,the simulation of M, from the initial configuration of M on input x.During the second phase M' repeatedly simulates a step of M by severalsteps of its own. The precise nature of the step to be simulated depends heavilyon the program counter K of M. As we said before, K is maintained in the state ofM'.
That is, the set of states of M' that are used during this phase are separatedinto p disjoint sets KJ U Kl U ... U K p , where p is the number of instructionsin the program II of M. The set of states K j "specializes" in simulating theinstruction 7rj of II. The precise nature of this part of M' depends of course onthe kind of the instruction 7rj. We shall give three indicative examples of howthis is done.Suppose first that 7rj is add 4, requiring that the contents of Register 4be added to those of Register o. Then M' will perform binary addition (recallExample 4.3.2) between its two tapes representing Registers 4 and 0, will leavethe result in the tape for Register 0, and then move to the first state of Kj+lto start the simulation of the next instruction.
If the instruction is, say, add= 33, then M' will start by writing the integer 33 in binary on the (k + 3)rdtape (the one heretofore unassigned to parts of M); the binary representation220Chapter 4: TURING MACHINESof the fixed integer 33 is "remembered" by the states of K j . Then it will add33 to the contents of Register 0, and finally it will erase the last tape and willmove to K j + 1 •Suppose next that 'Trj is write 2, requiring that the contents of the accumulator be copied to the tape square pointed at by Register 2. Then M' will addat the right end of the second tape - -the one where the contents of the tapeof M are kept in the (x, y) format- the pair (x, y), where x is the contents ofRegister 2 and y those of Register 0; both x and yare copied from the corresponding tapes of M'.
M' will then scan all other pairs (x',y') on the secondtape, comparing each x', bit by bit, with the contents of Register i. If a matchis found, the pair is erased, thus maintaining the integrity of the table. Thenthe state moves to K H1 , and the next instruction is executed.Suppose now that 'Trj is jpos 19, requiring that instruction 19 be executednext if Register 0 contains a positive integer.
Turing machine M' simply scansits tape representing Register 0; if a 1 is found in the binary representation ofthe integer in it, M moves to K 19 ; otherwise it moves to Kj+l.It is straightforward to simulate, in a very similar manner, all other kindsof instructions in the table of Figure 4-19. Eventually, M may reach a haltinstruction. If this happens, M' enters its third phase, translating M's outputto the Turing machine output conventions. If M is deciding a language, thenM' would read the contents of Register O.
If they are 1, it will halt at state y,if they are 0 it will halt at state n. If M is semideciding a language, then M'simply halts at state h. Finally, if M is computing a function, then M musttranslate the contents of the tape of M to a string in ~*, inverting the bijectionE, and then halt.It is clear from the preceding discussion that a k + 3-tape Turing machineM' can be designed that performs the above tasks -and hence, by Theorem4.3.1, a standard Turing machine can.To prove the second part of the theorem, we shall establish that t steps ofM on an input of size n can be simulated in O(t + n)3 time.
Naturally, theconstants in the 0 notation will, as usual, depend on the simulated machineM; for example they will depend on the largest constant (as in add = 314159)mentioned in the program of M.The O(t + n)3 bound is based on the following three observations:(a) At each step of M (including the addition and subtraction steps, see Problem 4.4.3) can be simulated in O( m) steps of M', where m is the total lengthof the nonblank parts of all tapes of M' -that is to say, the total length ofthe binary encodings of all integers in the current configuration of M.(b) The parameter m defined above can at each step increase by at most 0(1'),where l' is the length of the longest binary representation of any integerstored in the registers or tape squares of M. This is so because the increasecomes either from an add instruction or from a store instruction, and in4.5: Nondeterministic Turing Machines221both cases it is trivial to see that the increase can only be linear in r.(c) Finally, it is easy to see that r = O(t); that is, the length of the largestinteger represented by M can only increase by a constant at each step.The claimed bound follows by putting these three facts together.
•Problems for Section 4.44.4.1. Give explicitly the full details of the random access Turing machine programof Example 4.4.2. Give the sequence of configurations of this machine oninput aabccc.4.4.2. Give (in our abbreviated notation) a random access Turing machine program that decides the language {wcw: wE {a,b}'}.4.4.3. Show that, in the simulation in the proof of Theorem 4.4.2, each step can besimulated by O(m) steps of M', where m is the total length of M"s tapes.(You must establish that the 2-tape addition Turing machine in Example4.3.2 operates in linear time.) Can you estimate the constant in O(m)?4.4.4.
Suppose that our random access Turing machines had an explicit instructionmply. What goes wrong now in the second part of the proof of Theorem4.4.2?BNONDETERMINISTIC TURING MACHINESWe have added to our Turing machines many seemingly powerful features -multiple tapes and heads, even random access- with no appreciative increasein power. There is, however, an important and familiar feature that we have nottried yet: nondeterminism.We have seen that when finite automata are allowed to act nondeterministically, no increase in computational power results (except that exponentiallyfewer states may be needed for the same task), but that nondeterministic pushdown automata are more powerful than deterministic ones. We can also imagineTuring machines that act nondeterministically: Such machines might have, oncertain combinations of state and scanned symbol, more than one possible choiceof behavior.
Formally, a nondeterministic Turing machine is a quintuple(K,~,~, s, H), where K, ~, s, and H are as for standard Turing machines, and~ is a subset of ((K - H) x ~) x (K x (~ U {t-, -+} )), rather than a functionfrom (K - H) x ~ to K x (~ U {t-, -+}). Configurations and the relations f-- Mand f--M are defined in the natural way. But now f-- M need not be single-valued:One configuration may yield several others in one step.222Chapter 4: TURING MACHINESWhen Thring machines are allowed to act nondeterministically, is there anyincrease in computational power? We must first define what it means for a nondeterministic Turing machine to compute something. Since a nondeterministicmachine could produce two different outputs or final states from the same input, we have to be careful about what is considered to be the end result of acomputation by such a machine.
Because of this, it is easiest to consider at firstnondeterministic Turing that semidecide languages.Definition 4.5.1: Let M = (K,~,~, s, H) be a nondeterministic Turing machine. We say that M accepts an input w E (~- {c>,U})* if (s,C>Uw) f-M(h, uQv) for some h E H and a E ~,u, v E ~*. Notice that a nondeterministicmachine accepts an input even though it may have many nonhalting computations on this input input ~as long as at least one halting computation exists.We say that M semi decides a language L ~ (~ - {C>, U})* if the followingholds for all w E (~- {c>,u})*: wE L if and only if M accepts w.It is a little more subtle to define what it means for a nondeterministicTuring machine to decide a language, or to compute a function.Definition 4.5.2: Let M = (K,~,~, s, {y, n}) be a nondeterministic Turingmachine.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
