In this question, we consider Turing machines with a single tape. suppose we modify the machine to be a Splicing Turing machine STM. when a STM cuts a square out of the tape, it cuts the square where the head is currently located. After the cut, the head is located just to the right of the place where the square was cut out. For example, suppose the tape contents are abcde and the head is located at the d. If the STM inserts one square, then moves left two squares and cuts out one square, the resulting tape contents would be acd_e (where _ indicates a blank) and the head would be at the c.

a) briefly describe hoe every STM can be simulated using an ordinary Turing Machine.

b) Suppose you had a STM algorithm that took at most T(n) steps on all inputs of length n. Inserting a square into the tape or cutting a square out of the tape counts as a single step of the STM. Give a good upper bound on the number of steps an ordinary Turing machine would take when simulating the STM using the simulation you gave in part (a). If you like, you may use big-O notation to state your bound; you do not have to worry about constant factors. Explain Your answer please.