软硬件系统编程PPT (3).pdf

《软硬件系统编程PPT (3).pdf》由会员分享，可在线阅读，更多相关《软硬件系统编程PPT (3).pdf（24页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、图灵机与计算问题图灵机与计算问题 Turing Machine and Cumputability“Computability”here may be general 计算机是一种计算装置计算机是一种计算装置 Computer is a calculation equipment 为什么能够发明出计算机？为什么能够发明出计算机？Why computers can be invented?计算机的理论基础是什么？计算机的理论基础是什么？What is the theoretical basis of computers?British mathematician and logician Des

2、igned theoretical computer Connect computation with automatic mechanical operation“the father of theoretical computer science”3？Alan Mathison Turing 图灵机图灵机模型模型(Turing Model)Paper:“On Computable Numbers,with an Application to the Entscheidungsproblem”Gave a precise mathematical definition on computab

3、ility Turing Machine，TM A process of using machines to simulate an operation performed by people with pens and paper 4 将计算与自动进行的机械操作联系在将计算与自动进行的机械操作联系在一起一起 Connect Connect computation with automatic mechanical computation with automatic mechanical operationoperation The composition of Turing Model C

4、omposition:Type:A paper tape with infinite length Head:A read-write head States:A set of internal states Table:Table of Rules 5 BBX1X2XiXnBB读写头（状态qi）Three Actions of Turing Model 6 Paper Tape cell Tape Symbol Three Actions:Rewrite the current cell Move a cell left Or a cell right Contains a set of s

5、tates and rules(program)Working condition of Turing Machine Collection of input tape symbols Collection of internal states A set of control rules Working condition of Turing Machine 工作状态取决于规则和内部状态工作状态取决于规则和内部状态 Working condition depends on rules and internal stateWorking condition depends on rules a

6、nd internal state Working process of Turing Model 8 Working process of Turing Model:The read-write head reads the information from a cell of the paper tape；Check the table of rules based on the internal state；Determine the output action from one of the following three actions:Write information on th

7、e paper tape；The read-write head moves a cell forward；The read-write head moves a cell backward.Show the change of the internal state at the next moment.Turing Model Table of rules 9 Current Internal State S Input value i Output action O Internal State at the next moment S B 1 Move forward C A 0 Wri

8、te 1 on the paper tape B C 0 Move forward A Example of Turing Machine(1)10 Design an X+1 Turing Machine which requires the read-write head returns to its original position after the calculation is completed Analysis：collection of input tape symbols,collection of internal states,and a set of control

9、rules Assume：X=5,use 0 and 1 to represent it Design：collection of input symbols =0 0，1 1，*collection of internal states Q StartStart，addadd，carrycarry，noncarrynoncarry，overflowoverflow，returnreturn，halthalt Example of Turing Machine(2):Collection of control rules 11 Input Response Current state Curr

10、ent symbol New symbol Head moves New state Start*Left Add Add 0 1 Left Noncarry Add 1 0 Left Carry Add*Right Halt Carry 0 1 Left Noncarry Carry 1 0 Left Carry Carry*1 Left Overflow Noncarry 0 0 Left Noncarry Noncarry 1 1 Left Noncarry Noncarry *Right Return overflow 0或1*Right Return Return 0 0 Right

11、 Return Return 1 1 Right Return Return *stay Halt 12*1 0*1 Start Set the starting position of the read-write head to the most right side,and the content stored on the paper tape is 5 Example of Turing Machine(3)13*1 0*1 Add*1 0*1 Start According to the table,the readAccording to the table,the read-w

12、rite head moves a cell left,and the state write head moves a cell left,and the state becomes“add”becomes“add”input response Current state Current tape symbol New symbol Head move New state Start*Left Add*0 0*1 Carry input response Current state Current tape symbol New symbol Head move New state Star

13、t*Left Add Add 1 0 Left Carry*1 0*1 Add Do addition.If the content in the current cell if“1”,turn it into“0”,and the head moves a cell left.The internal state becomes“carry”.*0 1*1 Noncarry If the current state is“carry”and symbol in the cell is“0”,turn it into“1”,and the head moves a cell left.The

14、internal state becomes“carry”.*0 0*1 Carry input response Current state Current tape symbol New symbol Head move New state Start*Left Add Add 1 0 Left Carry Carry 0 1 Left Noncarry*0 1*1 Noncarry input response Current state Current tape symbol New symbol Head move New state Start*Left Add Add 1 0 L

15、eft Carry Carry 0 1 Left Noncarry Noncarry 1 1 Left Noncarry*0 1*1 Noncarry If the current state is“Nocarry”and symbol in the cell is“1”,keep it,and the head moves a cell left.The internal state remains the same.*0 1*1 Return input response Current state Current tape symbol New symbol Head move New

16、state Start*Left Add Add 1 0 Left Carry Carry 0 1 Left Noncarry Noncarry 1 1 Left Noncarry Noncarry *Right Return*0 1*1 Noncarry Operate according to the table：18 input response Current state Current tape symbol New symbol Head move New state Start*Left Add Add 1 0 Left Carry Carry 0 1 Left Noncarry

17、 Noncarry 1 1 Left Noncarry Noncarry *Right Return Return *stay Halt*0 1*1 Halt Operate according to the table：19 Is Turing Machine almighty？Understand Turing Machine-the greatness of it Human beings can be abstracted into Turing models Turing Model Collection of input Collection of output Internal

18、states A set of rules（or program）20 algorithm Computing is everywhere!What is Computing?Computing Computing is a transformation of information It transforms an input into an output.A confirmed process of transforming inputs into outputs with limited rules and steps Turing Machine A system that can t

19、ransform inputs into outputs through confirmed and limited steps and stops when it receives“halt”state.Turing Machine proves：Anything that can be done by Turing machine is calculable Turing Machine and Computing 21 Turing Machine is a computing device Not all questions are computable.What questions

20、are computable?图灵机图灵机模型模型 Turing Model 22 Turing model can be described as a quintuple：M=（Q，B，H）Among which：Q：collection of finite states：collection of input symbols：collection of control rules B：the original state,and B Q H：H Q,the halt state.Turing machine stops when the internal state is“halt”.23

21、 Complicated Turing machine can be built through the combination of many simple Turing machines Turing machine is the theoretical basis of computers The paper tape is like the storage in computers The head-write head is like the arithmetic unit Rules are like programs Both have internal states Turing machine and computers Conclusion Anything that cannot be done by Turing machine is not calculable Computers cannot solve all problems.It reflects on:Those cannot be finished within limited steps;Those are too complicated to be solved in acceptable time period though they are calculable.