0
$\begingroup$

I'm reading this book on Computational Complexity and on page 37, it has a proof that a bidirectional TM $M$ running in $T(n)$ time can be converted to a unidirectional TM $\widetilde M$ running $4T(n)$ time.

If $M$ uses alphabet $\Gamma$ then $\widetilde M$ will use the alphabet $\Gamma^2$ (i.e., each symbol in ’s alphabet corresponds to a pair of symbols in $M$’s alphabet). We encode a tape of $M$ that is infinite in both direction using a standard (infinite in one direction) tape by “folding” it in an arbitrary location, with each location of $\widetilde M$’s tape encoding two locations of $M$’s tape. At first, $\widetilde M$ will ignore the second symbol in the cell it reads and act according to $M$’s transition function. However, if this transition function instructs $\widetilde M$ to go "over the edge" of its tape then instead it will start ignoring the first symbol in each cell and use only the second symbol. When it is in this mode, it will translate left movements into right movements and vice versa. If it needs to go “over the edge” again then it will go back to reading the first symbol of each cell, and translating movements normally.

From this, why did they choose the factor of $4T(n)$? At most, this should be $2T(n)$ because it takes at most two steps in order to deal with going over the edge. Can someone please help me understand how it could be more than $2T(n)$?

Even if you don't have a complete answer, any ideas help. Thanks!

$\endgroup$
0
$\begingroup$

It seems that I encountered the same question. However, in my opinion, the answer should be T(n), not 2T(n). Because for each step in M, there is only one step in $ \widetilde M $corresponding to it.

$\endgroup$
  • $\begingroup$ Most of the time, each step in $M$ translates to one step in $\widetilde M$, but when the tape goes "over the edge," it takes one step in $M$, but two steps to do that in $\widetilde M$. Therefore, each step translates to at most two steps, so the upper bound is $2T(n)$. $\endgroup$ – Noble Mushtak May 25 '17 at 22:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.