A tape-saving Turing machine is similar to an ordinary (deterministic) one-tape Turing machine, but it can read and write on both sides of each tape square: front and back. In addition, it can move the head to the middle of nonblank portion of the tape. Specifically, if the first s squares of the tape are not blank, then the head can move to square ds/2e. At each step, the head of the tape-saving TM can move left (L), right (R), switch sides of the current square (S) or jump to the middle (J). (a) Please give a formal definition of the form of the transition function of tape-saving TM.
(b) Show that tape-saving TMs recognize the class of Turing-recognizable languages, that is, they have exactly the same power as ordinary TMs.