软硬件系统编程PPT (3).pdf
图灵机与计算问题图灵机与计算问题 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 Designed 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 computability 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 Composition: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 states 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 and 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 the 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 Write 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 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 Current 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 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-write 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 Start*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 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 Left 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 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 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 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 transform 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 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 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.
