3. (Part A) Give an informal description (implementation level description) of a Turing machine that takes as input a string of 0's and l's, interprets it as the binary representation of a nonnegative integer r; leaves as output the unary representation of 2 (i.e., a string of r l's). (Hint: it's probably easier to design a multitape Turing machine.] (Part B) A Turing machine with doubly infinite tape is similar to an ordinary Turing machine, but its tape is infinite to the left as well as to the right. The tape is initially filled with blanks except for the portion that contains the input. Computation is defined as usual except that the head never encounters an end to the tape as it moves leftward. Show that every Turing machine with doubly infinite tape has an equivalent single-tape Turing machine. [Hint: use a double-tape Turing machine to simulate it.] Solution