$($Problem $3\mathrm{.}11$ in the textbook$)$ A Turing machine with doubly

infinite tape is similar to an ordinary Turing machine, 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 usual except that the head

never encounters an end to the tape as it moves leftward. Show

that this if a Turing machine of this type accepts a language

$L,$ then there is a regular Turing machine $($as defined in class$)$

which also accepts $L.$

Hint: Suppose that the two$-$way infinite tape of the machine

contains input $a_{-m}{a}_{-m+1}dots{a}_{-2}{a}_{-1}{a}_0{a}_1{a}_{2}dots{a}_n,$ for some input

symbols $a_{i}in,$ which is preceded and followed by infinitely

many blanks to the left and to the right.

Imagine that we "fold" the two$-$way infinite tape in the fol$-$

lowing way

to turn it into two one$-$way infinite tapes $($# is a new symbol,

a delimiter.$)$ At the beginning, we may assume that

$a_{-1}=a_{-2}=$dots$=a_{-m}=$

since we can fold the tape at any position. When the head is to

the right of $a_0$ the simulation is on the upper tape; if the head is

to the left of $a_0,$ the simulation is on the lower tape. Your task

is to provide the details. You do not need to write the explicit

table of the transition function but define $Q,,$ as precisely

as possible and explain how the simulation proceeds.