1610906232-7ba7dbaea13262b50a6029d682cb7f1b (824370), страница 37
Текст из файла (страница 37)
Inthis chapter we take up the study of devices that can recognize this and manymore complicated languages. Although these devices, called Turing machinesafter their inventor Alan Turing (1912-1954), are more general than the automata previously studied, their basic appearance is similar to those automata.A Turing machine consists of a finite control, a tape, and a head that can beused for reading or writing on that tape. The formal defiuitions of Turing machines and their operation are in the same mathematical style as those used forfinite and pushdown automata. So in order to gain the additional computational power and generality of function that Turing machines possess, we shallnot move to an entirely new sort of model for a computer.Nevertheless, Turing machines are not simply one more class of automata,to be replaced later on by a yet more powerful type.
We shall see in this chapterthat, as primitive as Turing machines seem to be, attempts to strengthen themdo not have any effect. For example, we also study Turing machines with manytapes, or machines with fancier memory devices that can be read or writtenin a random access mode reminiscent of actual computers; significantly, thesedevices turn out to be no stronger in terms of computing power than basic Turingmachines. We show results of this kind by simulation methods: We can convertany "augmented" machine into a standard Turing machine which functions inan analogous way.
Thus any computation that can be carried out on the fanciertype of machine can actually be carried out on a Turing machine of the standardvariety. Furthermore, towards the end of this chapter we define a certain kind of179180Chapter 4: TURING MACHINESlanguage generator, a substantial generalization of context-free grammars, whichis also shown to be equivalent to the Turing machine.
From a totally differentperspective, we also pursue the question of when to regard a numerical function(such as 2x + x 2 ) as computable, and end up with a notion that is once moreequivalent to Turing machines!So the Turing machines seem to form a stable and maximal class of computational devices, in terms of the computations they can perform. In fact, inthe next chapter we shall advance the widely accepted view that any reasonableway of formalizing the idea of an "algorithm" must be ultimately equivalent tothe idea of a Turing machine.But this is getting ahead of our story. The important points to remember by way of introduction are that Turing machines are designed to satisfysimultaneously these three criteria:(a) They should be automata; that is, their construction and function shouldbe in the same general spirit as the devices previously studied.(b) They should be as simple as possible to describe, define formally, and reasonabout.(c) They should be as general as possible in terms of the computations theycan carry out.Now let us look more closely at these machines.
In essence, a Turing machineconsists of a finite-state control unit and a tape (see Figure 4-1). Communicationbetween the two is provided by a single head, which reads symbols from the tapeand is also used to change the symbols on the tape. The control unit operatesin discrete steps; at each step it performs two functions in a way that dependson its current state and the tape symbol currently scanned by the read/writehead:(1) Put the control unit in a new state.(2) Either:(a) Write a symbol in the tape square currently scanned, replacing the onealready there; or(b) Move the read/write head one tape square to the left or right.The tape has a left end, but it extends indefinitely to the right. To preventthe machine from moving its head off the left end of the tape, we assume that theleftmost end of the tape is always marked by a special symbol denoted by 1>; weassume further that all of our TUring machines are so designed that, wheneverthe head reads a 1>, it immediately moves to the right.
Also, we shall use thedistinct symbols +- and -+ to denote movement of the head to the left or right;we assume that these two symbols are not members of any alphabet we consider.A Turing machine is supplied with input by inscribing that input stringon tape squares at the left end of the tape, immediately to the right of the I>1814.1: The definition of a Turing MachineRead/write head(moves in both directions)h-qlFinite controlFigure 4-1symbol. The rest of the tape initially contains blank symbols, denoted U.
Themachine is free to alter its input in any way it sees fit, as well as to write on theunlimited blank portion of the tape to the right. Since the machine can move itshead only one square at a time, after any finite computation only finitely manytape squares will have been visited.We can now present the formal definition of a Turing machine.Definition 4.1.1: A Turing machine is a quintuple (K,~, J, s, H), whereK is a finite set of states;~ is an alphabet, containing the blank symbol U and the left end symbolc>, but not containing the symbols f- and -+;s E K is the initial state;H ~ K is the set of halting states;J, the transition function, is a function from (K - H) x ~ to K x (~U {f, -+ }) such that,(a) for all q E K - H, if J(q, c» = (p, b), then b =-+(b) for all q E K - H and a E ~, if J(q, a) = (p, b) then b ¥- c>.If q E K - H, a E ~, and J(q, a) = (p, b), then M, when in state q andscanning symbol a, will enter state p, and (1) if b is a symbol in ~, M willrewrite the currently scanned symbol a as b, or (2) if b is f- or -+, M will moveits head in direction b.
Since J is a function, the operation of M is deterministicand will stop only when M enters a halting state. Notice the requirement (a)on J: When it sees the left end of the tape c>, it must move right. This way theleftmost C> is never erased, and M never falls off the left end of its tape. By (b),M never writes a c>, and therefore C> is the unmistakable sign of the left end of182Chapter 4: TURING MACHINESthe tape. In other words, we can think of c> simply as a "protective barrier" thatprevents the head of M from inadvertently falling off the left end, which doesnot interfere with the computation of M in any other way.
Also notice that J isnot defined on states in H; when the machine reaches a halting state, then itsoperation stops.Example 4.1.1: Consider the Turing machine M =(K,~,J, s, {h}), whereK ={qo,ql,h},~={a,u,c>},s =qo,and J is given by the following table.aJ(q,a)qoqoqoauqlqlqla(ql, u)(h,u)(qo, -+)(qo, a)(qo, -+)(ql, -+)q,c>Uc>When M is started in its initial state qo, it scans its head to the right,changing all a's to u's as it goes, until it finds a tape square already containingu; then it halts. (Changing a nonblank symbol to the blank symbol will becalled erasing the nonblank symbol.) To be specific, suppose that M is startedwith its head scanning the first of four a's, the last of which is followed by a u.Then M will go back and forth between states qo and ql four times, alternatelychanging an a to a U and moving the head right; the first and fifth lines of thetable for J are the relevant ones during this sequence of moves.
At this point,M will find itself in state qo scanning U and, according to the second line ofthe table, will halt. Note that the fourth line of the table, that is, the valueof J(ql,a), is irrelevant, since M can never be in state ql scanning an a if it isstarted in state qo. Nevertheless, some value must be associated with J(ql, a)since J is required to be a function with domain (K - H) x ~.¢Example 4.1.2: Consider the Turing machine M =K ={qo,h},~={a,u,c>},s =qo,H ={h},(K,~,J, s, H), where1834.1: The definition of a Turing Machineq,qoqoqo(JJ(q, (J)a(qo, f-)(h,u)(qO, -+)UC>and 15 is given by this table.This machine scans to the left until it finds a U and then halts.
If everytape square from the head position back to the left end of the tape contains ana, and of course the left end of the tape contains a c>, then M will go to the leftend of the tape, and from then on it will indefinitely go back and forth betweenthe left end and the square to its right. Unlike other deterministic devices thatwe have encountered, the operation of a Turing machine may never stop.OWe now formalize the operation of a Turing machine.To specify the status of a Turing machine computation, we need to specifythe state, the contents of the tape, and the position of the head. Since allbut a finite initial portion of the tape will be blank, the contents of the tapecan be specified by a finite string. We choose to break that string into twopieces: the part to the left of the scanned square, including the single symbolin the scanned square; and the part, possibly empty, to the right of the scannedsquare.
Moreover, so that no two such pairs of strings will correspond to thesame combination of head position and tape contents, we insist that the secondstring not end with a blank (all tape squares to the right of the last one explicitlyrepresented are assumed to contain blanks anyway). These considerations leadus to the following definitions.Definition 4.1.2: A configuration of a Turing machine M =a member of K x C>~* x (~'(~ - {u}) U {e}).(K,~,15, s, H) isThat is, all configurations are assumed to start with the left end symbol,and never end with a blank -unless the blank is currently scanned. Thus(q, c>a, aba), (h, C> U UU, Ua), and (q, C> U a U U, e) are configurations (see Figure4-2), but (q, c>baa, a, bcU) and (q, Uaa, ba) are not. A configuration whose statecomponent is in H will be called a halted configuration.We shall use a simplified notation for depicting the tape contents (includingthe position of the head): We shall write WQU for the tape contents of theconfiguration (q, wa, u); the underlined symbol indicates the head position.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
