Page 1 1 Turing Machines Page 2 1 Turing Machines 2 Turing Machines are… n Very powerful (abstract) machines that could simulate any modern day computer (although very, very slowly!) n Why design such a machine? n If a problem cannot be “solved” even using a TM, then it implies that the problem is undecidable n Computability vs. Decidability For every input, answer YES or NO Page 3 1 Turing Machines 2 Turing Machines are… n Very powerful (abstract) machines that could simulate any modern day computer (although very, very slowly!) n Why design such a machine? n If a problem cannot be “solved” even using a TM, then it implies that the problem is undecidable n Computability vs. Decidability For every input, answer YES or NO 3 A Turing Machine (TM) n M = (Q, ?, G, d, q 0 ,B,F) BBBX 1 X 2 X 3 … X i … X n BB … … Finite control Infinite tape with tape symbols B: blank symbol (special symbol reserved to indicate data boundary) Input & output tape symbols Tape head This is like the CPU & program counter Tape is the memory Page 4 1 Turing Machines 2 Turing Machines are… n Very powerful (abstract) machines that could simulate any modern day computer (although very, very slowly!) n Why design such a machine? n If a problem cannot be “solved” even using a TM, then it implies that the problem is undecidable n Computability vs. Decidability For every input, answer YES or NO 3 A Turing Machine (TM) n M = (Q, ?, G, d, q 0 ,B,F) BBBX 1 X 2 X 3 … X i … X n BB … … Finite control Infinite tape with tape symbols B: blank symbol (special symbol reserved to indicate data boundary) Input & output tape symbols Tape head This is like the CPU & program counter Tape is the memory 4 Transition function n One move (denoted by |---) in a TM does the following: n d(q,X) = (p,Y,D) n q is the current state n X is the current tape symbol pointed by tape head n State changes from q to p n After the move: n X is replaced with symbol Y n If D=“L”, the tape head moves “left” by one position. Alternatively, if D=“R” the tape head moves “right” by one position. q p X / Y ,D You can also use: è for R ç for L Page 5 1 Turing Machines 2 Turing Machines are… n Very powerful (abstract) machines that could simulate any modern day computer (although very, very slowly!) n Why design such a machine? n If a problem cannot be “solved” even using a TM, then it implies that the problem is undecidable n Computability vs. Decidability For every input, answer YES or NO 3 A Turing Machine (TM) n M = (Q, ?, G, d, q 0 ,B,F) BBBX 1 X 2 X 3 … X i … X n BB … … Finite control Infinite tape with tape symbols B: blank symbol (special symbol reserved to indicate data boundary) Input & output tape symbols Tape head This is like the CPU & program counter Tape is the memory 4 Transition function n One move (denoted by |---) in a TM does the following: n d(q,X) = (p,Y,D) n q is the current state n X is the current tape symbol pointed by tape head n State changes from q to p n After the move: n X is replaced with symbol Y n If D=“L”, the tape head moves “left” by one position. Alternatively, if D=“R” the tape head moves “right” by one position. q p X / Y ,D You can also use: è for R ç for L 5 ID of a TM n Instantaneous Description or ID : n X 1 X 2 …X i-1 qX i X i+1 …X n means: n q is the current state n Tape head is pointing to X i n X 1 X 2 …X i-1 X i X i+1 …X n are the current tape symbols n d(q,X i ) = (p,Y,R) is same as: X 1 …X i-1 qX i …X n |---- X 1 …X i-1 YpX i+1 …X n n d(q,X i ) = (p,Y,L) is same as: X 1 …X i-1 qX i …X n |---- X 1 …pX i-1 YX i+1 …X nRead More

Offer running on EduRev: __Apply code STAYHOME200__ to get INR 200 off on our premium plan EduRev Infinity!

18 videos|44 docs|39 tests