DOC PREVIEW
IUPUI CSCI 23000 - Models of Computation - Turing Machines

This preview shows page 1-2-3 out of 9 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 9 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 9 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 9 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 9 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Models of Computation - Turing MachinesThe Turing Machine (TM)Slide 3Slide 4Slide 5Unary Representation for TMSlide 7Slide 8Slide 9Dale RobertsDepartment of Computer and Information Science,Department of Computer and Information Science,School of Science, IUPUISchool of Science, IUPUICSCI 230Models of ComputationModels of Computation - Turing Machines - Turing MachinesDale Roberts, LecturerComputer Science, IUPUIE-mail: [email protected] RobertsThe Turing Machine (TM)The Turing Machine (TM)Turing Machine is a model of computing agent. Turing Machine is a model of computing agent. It is a pencil-and-paper type model that captures the essential It is a pencil-and-paper type model that captures the essential features of a computing agent.features of a computing agent.A Turing machine consists ofA Turing machine consists of1.1.a tape that extends infinitely in both directionsa tape that extends infinitely in both directions2.2.the tape is divided into cells, each cell can carry a symbol.the tape is divided into cells, each cell can carry a symbol.3.3.the symbols comes from a finite set of symbols called the the symbols comes from a finite set of symbols called the alphabetalphabet4.4.the the alphabet alphabet consists of symbols : b (blank), 0, 1, and special consists of symbols : b (blank), 0, 1, and special symbols X, Y, $symbols X, Y, $5.5.the tape serve as memorythe tape serve as memory6.6.has a finite number of has a finite number of kk states, states, 1, …k1, …k. . b b 0 1 1 b b .1Dale RobertsTuring Machine actions depend on two inputs:Turing Machine actions depend on two inputs:1.1.The current state of the machineThe current state of the machine2.2.content of cell currently being read (input)content of cell currently being read (input)A Turing machine can do only one operation at A Turing machine can do only one operation at a time. Each time an operation is done, three a time. Each time an operation is done, three actions may take place:actions may take place:3.3.write a symbol to cellwrite a symbol to cell4.4.go into a new statego into a new state5.5.move one cell left or rightmove one cell left or rightDale Robertscurrent stateThe Turing Machine (TM)The Turing Machine (TM). . b b 0 1 1 b b .1. . b b 1 1 1 b b .121 20/1RState: where you are now.RWYour movementoutputinputState Transition:ExampleExample: Assume a Turing machine (TM) instruction:: Assume a Turing machine (TM) instruction: if you are in state if you are in state 11 and and you are reading symbol 0you are reading symbol 0then then write symbol 1 onto tapewrite symbol 1 onto tape go into state go into state 22 move move rightrightnext stateoutputinputaction (direction)Written as: Written as: (1,0,1,R,2)(1,0,1,R,2)Dale RobertsThe Turing Machine (TM)The Turing Machine (TM)ExampleExample: Design a Turing Machine which will invert the string of binary digits: Design a Turing Machine which will invert the string of binary digitsif the input string is 10110 then the output string should be 01001if the input string is 10110 then the output string should be 01001let us draw a state diagramlet us draw a state diagramThe TM instruction sets will beThe TM instruction sets will be(1,0,1,R,1)(1,0,1,R,1)(1,1,0,R,1)(1,1,0,R,1)Let the initial configuration beLet the initial configuration be: ... b : ... b 11 0 1 1 0 b ... 0 1 1 0 b ...... b ... b 11 0 1 1 0 b ... 0 1 1 0 b ... ... b 0 ... b 0 00 1 1 0 b ... 1 1 0 b ...... b 0 1 ... b 0 1 11 1 0 b ... 1 0 b ...... b 0 1 0 ... b 0 1 0 11 0 b ... 0 b ...... b 0 1 0 0 ... b 0 1 0 0 00 b ... b ...... b 0 1 0 0 1 ... b 0 1 0 0 1 bb ... ...11/00/1Dale RobertsUnary representation is used in order to do any arithmetic operations on a TM.Unary representation is used in order to do any arithmetic operations on a TM.Unary representation looks as followsUnary representation looks as follows0 0  1 11 1  11 112 2  111 1113 3  1111 11114 4  11111 11111ExampleExample: Design a Turing Machine to add 1 to any number: Design a Turing Machine to add 1 to any numberstart in state 1start in state 1if the state is 1 and current input is 1, write 1 and move right and stay in state 1if the state is 1 and current input is 1, write 1 and move right and stay in state 1if the current state is 1 and current input is b, write 1 and move to state 2 and move right if the current state is 1 and current input is b, write 1 and move to state 2 and move right and HALTand HALTTM instructions:TM instructions:(1,1,1,R,1)(1,1,1,R,1)(1,b,1,R,2) (1,b,1,R,2) state 2 does not exist, so haltstate 2 does not exist, so haltLet the initial configuration be:Let the initial configuration be: ... b 1 1 1 b ... ... b 1 1 1 b ...... b ... b 11 1 1 b ... 1 1 b ... ... b 1 ... b 1 11 1 b ... 1 b ...... b 1 1 ... b 1 1 11 b ... b ...... b 1 1 1 ... b 1 1 1 bb ... ...... b 1 1 1 1 ... b 1 1 1 1 bb ... ...Unary Representation for TMUnary Representation for TM1 2b/1R1/1Halt2 in unary representation3 in unary representations1s1s1s1s2Dale RobertsExampleExample: Adding of two non-zero numbers (unary representation): Adding of two non-zero numbers (unary representation) Initial SetupInitial Setup. . b 1 1 1 b 1 1 b . . . . b 1 1 1 b 1 1 b . . Answer should be:Answer should be:. . b b b 1 1 1 1 b . .. . b b b 1 1 1 1 b . .(1,1,b,R,2): Erase leftmost 1 and move right(1,1,b,R,2): Erase leftmost 1 and move right(2,1,b,R,3): Erase second 1 and move right(2,1,b,R,3): Erase second 1 and move right(3,1,1,R,3): pass over any 1’s until a blank is found(3,1,1,R,3): pass over any 1’s until a blank is found(3,b,1,R,4): write 1 over the blank(3,b,1,R,4): write 1 over the blank(4,1,1,R,4): pass over remaining 1’s(4,1,1,R,4): pass over remaining 1’s(4,b,b,R,5): halt(4,b,b,R,5): halt1 21/bR31/bR4b/1R5b/bR1/11/1HaltS1... b 1 1 1 b 1 1 b...S2... b b 1 1 b 1 1 b...S3... b b b 1 b 1 1 b...S3... b b b 1 b 1 1 b...S4... b b b 1 1 1 1 b...S4... b b b 1 1 1 1 b...S4... b b b 1 1 1 1 b...Dale RobertsExampleExample: Add two numbers, 2 + 3: Add two numbers, 2 + 3initial setup would: a ‘initial setup would: a ‘bb’ separate the two numbers.’ separate the two numbers.... b ... b 1 1 11 1 1 b b 1 1 1 11 1 1 1 b ... b ... 22 3 3and the expected answer isand the expected answer is... b ... b 1 1 1 1 1 11 1 1 1 1 1 b ... b ...55The TM instruction sets will beThe TM instruction sets will


View Full Document

IUPUI CSCI 23000 - Models of Computation - Turing Machines

Download Models of Computation - Turing Machines
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Models of Computation - Turing Machines and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Models of Computation - Turing Machines 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?