Problem 3. A Turing machine with doubly infinite tape is similar to the ordinary Turing ma- chine defined in class (i.e., a Turing machine whose tape is only infinite on one side), 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 for the ordinary Turing machine (formally we will define this on Friday) except that the head never encounters an end to the tape as it moves leftward. Prove that a Turing machine M with doubly infinite tape can be simulated by an ordinary Turing machine M. You dont have to describe the simulation in complete detail, but you should describe it well enough to say (i) how many states and tape symbols M' needs in terms of how many M has, and (i) how many computation steps M requires for the simulation in terms of the number of computation steps of M. Show that this type of Turing machine recognizes the class of Turing-recognizable languages (i.e., the languages accepted by ordinary Turing machines) Problem 3. A Turing machine with doubly infinite tape is similar to the ordinary Turing ma- chine defined in class (i.e., a Turing machine whose tape is only infinite on one side), 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 for the ordinary Turing machine (formally we will define this on Friday) except that the head never encounters an end to the tape as it moves leftward. Prove that a Turing machine M with doubly infinite tape can be simulated by an ordinary Turing machine M. You dont have to describe the simulation in complete detail, but you should describe it well enough to say (i) how many states and tape symbols M' needs in terms of how many M has, and (i) how many computation steps M requires for the simulation in terms of the number of computation steps of M. Show that this type of Turing machine recognizes the class of Turing-recognizable languages (i.e., the languages accepted by ordinary Turing machines)