Turing machine with the doubly in finite tape is one where the machine's read head can move left to the beginning of input string as well as right of end of the input string. All tape cells not part of the input string, in both the directions, initially comprises of the blank character ".
a) Turing machines with doubly infinite tapes are explained utilizing the same 7-tuple as Turing machines (with singly infi nite tapes) described in class and in Sipser; start configurations and accepting the configurations are also the same. Though, the rules for how a configuration Ci yields a configuration Ci+1 are different. Provide the rules for how Ci yields Ci+1 for the Turing machine with doubly infinite tape, involving the special-case rules which apply when the machine's read head is close to the either edge of area it has utilized so far on the tape.
b) Describe how to simulate the Turing machine along with singly infinite tape on the Turing machine with the doubly infinite tape. (Be sure to handle the can't move left" special case.)
c) Describe how to simulate the Turing machine with the doubly infinite tape on a Turing machine with singly infinite tape.