《《计算机科学导论》课件Unit-14Theory-of-Computation》由会员分享，可在线阅读，更多相关《《计算机科学导论》课件Unit-14Theory-of-Computation（41页珍藏版）》请在装配图网上搜索。
1、*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,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 Ullm
2、an 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-
3、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 cal
4、culate 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
5、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,i
6、t 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 ha
7、s 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 consi
8、sts 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
9、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
10、 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 auto
11、maton,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 se
12、t 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 des
13、cription,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
14、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 hav
15、e 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 Tur
16、ing 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.,
《计算机科学导论》课件Unit-14Theory-of-Computation
