$4.$ TM Variants $(10$ points$)($Graded for completeness$)$ The textbook defines Turing machines

as finite state automata with a read$/$write tape that extends indefinitely to the right. If the Turing

machine attempts to move beyond the left hand boundary of the tape, the tape head simply stays

in its current position. JFLAP allows a seemingly more powerful type of Turing machine, whose

tape in unbounded both to the left and to the right, and if the machine attepts to move beyond

the left margin, a new blank cell is created to allow moving left. In this problem you are asked

to give a formal definition of this extended Turing machine, and explain why it is equivalent to

the one defined in the textbook.

$($a$)$ Give a formal definition of this new type of TM$.$ Your definition should include

$$ the definition of a machine as a tuple of sets and functions

$$ an appropriate set of configurations

$$ an appropriate transition relation between configurations

$$ the set of strings accepted by the machine

$($b$)$ Prove that this new type of TM is not more powerful than the Turing machine as defined in

the textbook, giving a method to transform any extended Turing machine $($with doubly infinite

tape$)$ into an equivalent regular Turing machine. Describe your transformation in detail, either

by giving a formal description of the resulting Turing machine, or by providing an accurate low

level description of all the steps it performs.