Question 4, PS 2: You should assume that x is a string of 0s and 1s. The Turing machine that you design may write any symbol from {0,1,b}. The main difficulty (from the questions people ask) is how to tell the middle of the string xx. One way to do it is to implement a counter; the Turing machine may use the portion of the tape to the left of xx to compute the number of bits of xx and divide it by two. There is, however, a simpler way to do it: let the TM go back in forth on the string xx, moving bits on the right end to the right, and on the left end to the left, for example if x=101, so that xx=101101, the TM would do the following: 101101 --> 1b01101 --> 1b0110b1 --> 10b110b1 --> 10b11b01 --> 101b1b01 --> 101bb101 (note that these are not single steps, "-->" means several steps of your Turing machine), and once bb are together, the TM knows that it has xbbx on the tape, so it has successfully "divided" the string in two. Of course you have to provide for cases where this cannot be done (for example, if the input has an odd number of bits--so it is not of the form xx--then the string would have to be rejected). Once you have xbbx on the input tape, the TM can now check that x=x; again it may be the case that you have xbby, where x is not y, in which case the TM must reject this input.