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.