资源描述
*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,Unit 14,Theory of Computation,2,14-1 The Turing Machine,14-2 Halting Problem,14-3 Solvable Problems,14-4 References and Recommended Reading,14-5 Summary,14-6 Practice Set,OUTLINE,3,Understand the architecture of Turing machine.,Understand Hopcroft and Ullman formally how to define a Turing machine as a 7-tuple,.,Understand the Church-Turing thesis.,After reading this chapter,you are supposed tobe able to:,OBJECTIVES,Understand halting problem,polynomial problem,and non-polynomial problem.,4,Informal description,Formal description,Examples,The Church-Turing thesis,14-1,The Turing Machine,5,Before Turing Machine,The Turing machine,is an abstract machine devised by Alan Mathison Turing in 1936 to simulate mathematical operation,and is the foundation of,modern computers,.Turing shows that a machine with the correct minimal set of operations can calculate anything that is computable,no matter what the complexity is.,Today,the common computer usually has a finite memory,but here we suppose that the Turing machines memory is infinite.In this section,we present a very,simplified version,of the machine to show how Turing machine works.,6,Informal description,The Turing machine mathematically models a machine that can operate on a tape.The tape holds symbols,which the machine may read and write,one at a time using the tape head.The behavior is fully decided by a finite set of,fundamental instructions,like in state 50,if the symbol seen is 0,it will write 1;if the symbol seen is 1,it will become state 17;in this state,if the symbol seen is 0,it will write 1 and then become state 6;etc.,7,Informal description,More precisely,a Turing machine contains:a tape,a controller,and a read/write head.Its structure is shown in Figure 14.1.Someone has created a machine that embodied the classic look and feel of the machine presented in Turings paper(Figure 14.2).,Figure 14.1 The Turing machine,Informal description,Figure 14.2 The Turing machine in the classic style,8,(1)Tape,The tape contains several,cells,one next to the other.Every cell consists of a symbol from,the finite alphabet,.For the sake of simplicity,we suppose that the machine here may accept only two symbols:a blank(b)and digit 1.The tape used here is,freely,extendable,to the right and to the left,i.e.,the Turing machine consist of infinite tape needed for its computation.We also suppose that the tape can deal with only positive integer data made up only of 1s.For instance,the integer 6 is represented as 111111(six 1s).0 is represented by the absence of 1s.,(2)Read/Write Head,The,read/write head,can read and write symbols on the tape and move to the left or to the right one(and only one)cell at a time.In some models the tape moves and the head is stationary,whereas in some models,the head moves and the tape remains stationary.,(3)Controller,The,controller,functionally acts like the,central processing unit(CPU),in modern computers.Actually,it is a,finite state automaton,a machine that has finite states and can move from one state to another depending on the input.,Informal description,9,10,Formal description,Hopcroft and Ullman formally define a Turing machine as a 7-tuple:,M=Q,T,b,I,q,0,F,where,Q,is a finite,non-empty set of states,T is a finite,non-empty set of tape alphabet symbols,B T is the,blank symbol,(the only symbol allowed to occur on the tape infinitely often at any step during the computation),I T-b is the set of input symbols,q,0,Q is the initial state,F Q is the set of final or accepting states,=QT,Q(TL,R,N)is a partial function,Formal description,called,the transition,function,where L is,left shift,R is,right shift,and N is no shift.,Anything that operates according to these specifications is a Turing machine.The 7-tuple for the 4-state looks like this:,Q=A,B,C,D,T=b,1,I=1,q,0,=A,F=D,=see transition table(Table 14.1)below,11,Formal description,12,Table 14.1 Transition table for the Turing machine,Current state,Read,Write,Move,New state,C,b,1,L,D,C,1,1,N,A,B,b,b,R,C,B,1,1,L,D,A,b,1,L,B,A,1,b,R,A,Formal description,We can create instructions to put together the value of five columns in each row.For this elementary machine,we have only six instructions:,13,1.(C,b,1,L,D)2.(C,1,1,N,A)3.(B,b,b,R,C),4.(B,1,1,L,D)5.(A,b,1,L,B)6.(A,1,b,R,A),Formal description,14,The transition state,diagram for the Turing machine is shown in Figure 14.3.,Figure 14.3 Transition state diagram for the Turing machine,Examples,(1)Example 14.1,If a Turing machine with the above six instructions starts with the configuration shown in Figure 14.4,what will be the configuration of the machine after the execution of one of the above instructions?,The machine is in state B and the current symbol is 1,which means that only the,second instruction,(B,1,1,L,D),can be carried out.The new configuration is also shown in Figure 14.4.After execution,the state of the controller has been altered to D and the read/write head has moved one symbol to the left.,
展开阅读全文