Models of Computation - State Transition DiagramsModels of ComputationSlide 3Model of a Computing AgentSlide 5A Concept of a StateState Transition DiagramsSlide 8Dale RobertsDepartment of Computer and Information Science,Department of Computer and Information Science,School of Science, IUPUISchool of Science, IUPUICSCI 230Models of ComputationModels of Computation - State Transition Diagrams - State Transition DiagramsDale Roberts, LecturerComputer Science, IUPUIE-mail: [email protected] RobertsModels of ComputationModels of ComputationWhat is a model?What is a model?Capture the Capture the importantimportant properties of the real thing properties of the real thingprobably be different in scale from the real thingprobably be different in scale from the real thingsuppress details of the real thingsuppress details of the real thinglack full functionality of the real thinglack full functionality of the real thingExampleExample: A model to compute the distance traveled for a moving vehicle:: A model to compute the distance traveled for a moving vehicle:d = r*t or t = d/rd = r*t or t = d/rdd = distance; = distance; rr = rate of speed; = rate of speed; t t = time= timeDale RobertsWhy we need models if they are not the Why we need models if they are not the real thing?real thing?By changing some aspects, we can observe their By changing some aspects, we can observe their effectseffectsCan provide an environment for learningCan provide an environment for learningThey can be used as design tools without actually They can be used as design tools without actually building the real thing – for economic reasonsbuilding the real thing – for economic reasonsIn summary, they can be predict, can be used for In summary, they can be predict, can be used for training, can be used as test beds.training, can be used as test beds.Dale RobertsModel of a Computing AgentModel of a Computing AgentQ:Q:Operations in an algorithm must be unambiguous Operations in an algorithm must be unambiguous and effectively and effectively computablecomputable. Therefore, could we . Therefore, could we design a model of an algorithm before we design a model of an algorithm before we implement the algorithm in hardware and /or implement the algorithm in hardware and /or software? software? A:A:A computing agent (robot) is a thing/a person that A computing agent (robot) is a thing/a person that carries out the operations described in an algorithm.carries out the operations described in an algorithm.Dale RobertsProperties of a Computing AgentProperties of a Computing Agentcan accept an can accept an inputinputcan store & retrieve information from can store & retrieve information from memorymemorycan take can take actionsactions according to instructions – the actions according to instructions – the actions may depend upon a may depend upon a present statepresent state and the and the current inputcurrent inputcan produce an can produce an outputoutputAgentAgentSo, what is a So, what is a StateState??EnvironmentEnvironmentInputOutputmotoragent?Dale RobertsConsider a simple scenario:Consider a simple scenario:If I am in my office:If I am in my office:if the phone rings; I’ll answer the phone and leave my officeif the phone rings; I’ll answer the phone and leave my officeif the phone does not ring; I’ll not answer the phone and will stay in the officeif the phone does not ring; I’ll not answer the phone and will stay in the officeIf I am NOT in my office:If I am NOT in my office:if the phone rings; I’ll NOT answer the phone but I’ll come back to my officeif the phone rings; I’ll NOT answer the phone but I’ll come back to my officeif the phone does not ring; I’ll not answer it and will stay away from the officeif the phone does not ring; I’ll not answer it and will stay away from the officeA Concept of a StateA Concept of a StatePhone ring I am in office Answer I will be in office?1 1 1 00 1 0 11 0 0 10 0 0 0Office0/1Phone0/1(input)Answer the Phone0/1(output)function notationDale RobertsState Transition DiagramsState Transition DiagramsOutput depends NOT ONLY on the INPUT, but also Output depends NOT ONLY on the INPUT, but also depends on the internal (current) state of the office (0/1).depends on the internal (current) state of the office (0/1).LetLetAA: is a state when I’m in the office: is a state when I’m in the officeBB: is a state when I’m : is a state when I’m NOTNOT in the office in the officeState TableState TableState Transition DiagramState Transition DiagramPresent State Next State (Output)phone = 0 phone = 1A A, 0 B, 1B B, 0 A, 0A B1 / 11 / 00 / 00 / 0in office out of officeDale RobertsState Transition DiagramsState Transition DiagramsWhat does the following state transition diagram What does the following state transition diagram do?do?A