1. Consider the Turing machine T over the input alphabet = {0, 1} with the state...

  

Transcribed Image Text:

1. Consider the Turing machine T over the input alphabet = {0, 1} with the state diagram below (the tape alphabet is = {0, 1, }). Convention: any missing transitions in the state diagram have value (grej,, R) 90 0:0. R. 1:0 R 0:0, R 1:1,L qacc 0:0 R DDR 41 grej (a) (5 points) Find a string of length 2 that is accepted by this Turing machine and justify your answer by describing the computation of T on this string. Your description should mention the contents of the tape, the state of the machine, and the location of the read/write head at each step in the computation. Hint: In class slides we've drawn pictures to represent the configuration of the machine at each step in a computation. You may do so or you may choose to describe these configura- tions in words. (c) (20 points) T is not a decider (Bonus, not for credit: how would you prove this?). Change the machine by changing one arrow in the state diagram to create a new Turing machine that is a decider. In other words, fill in the blank below in the formal definition of the Turing machines Tnew Tnew({90, 91, qacc, qrej}, {0, 1}, {0, 1, }, new, 90, qacc, grej) = where Snew ((q, x)) == -(((-)) if q = x= ((q, x)) otherwise where d is the transition function for T. Include in your explanation all of the following: ⚫ The full definition of new and the state diagram of Tnew A description of L(Tnew), using the state diagram to explain which strings are accepted and which are not. ⚫ A description, using the state diagram, to explain why all computations of Tnew halt. 1. Consider the Turing machine T over the input alphabet = {0, 1} with the state diagram below (the tape alphabet is = {0, 1, }). Convention: any missing transitions in the state diagram have value (grej,, R) 90 0:0. R. 1:0 R 0:0, R 1:1,L qacc 0:0 R DDR 41 grej (a) (5 points) Find a string of length 2 that is accepted by this Turing machine and justify your answer by describing the computation of T on this string. Your description should mention the contents of the tape, the state of the machine, and the location of the read/write head at each step in the computation. Hint: In class slides we've drawn pictures to represent the configuration of the machine at each step in a computation. You may do so or you may choose to describe these configura- tions in words. (c) (20 points) T is not a decider (Bonus, not for credit: how would you prove this?). Change the machine by changing one arrow in the state diagram to create a new Turing machine that is a decider. In other words, fill in the blank below in the formal definition of the Turing machines Tnew Tnew({90, 91, qacc, qrej}, {0, 1}, {0, 1, }, new, 90, qacc, grej) = where Snew ((q, x)) == -(((-)) if q = x= ((q, x)) otherwise where d is the transition function for T. Include in your explanation all of the following: ⚫ The full definition of new and the state diagram of Tnew A description of L(Tnew), using the state diagram to explain which strings are accepted and which are not. ⚫ A description, using the state diagram, to explain why all computations of Tnew halt.

Answer rating: 100% (QA)

c Consider the string 01 when given as input to the Turing machine The initial configuration will be q001 ie the state is q0 and head points at the lo... View the full answer