# How to simulate a bidirectional TM on a regular one with time factor four?

In Computational Complexity A Modern Approach, one claim says that if $f$ is computable in time $T(n)$ by a bidirectional TM $M$, then it is computable in time $4T(n)$ by a unidirectional TM $\tilde{M}$. How to work out the constant $4$?

In my opinion, in addition to "go over the edge" operation, one transition in $M$ corresponds to one transition in $\tilde{M}$, so where does constant $4$ come from?

• There is no proof in the book? Have you tried working out how a TM would simulate a bidirectional TM? – Raphael Aug 3 '14 at 20:49
• This is about Claim 1.8 in Arora&Barak: Computational Complexity: A Modern Appproach, found on page 21. The book has loads of stuff in it where the actual proofs are left to the reader, while some other things only have proof sketches - this one falls in the latter category. I remember reading the first third of the book and often thinking "this bound is unnecessarily loose" - after skimming the paragraph now, I get the impression that this is the case here as well. – G. Bach Aug 4 '14 at 2:45
• My advice is not to worry too much about the constants; the point of all these bits in the first chapter is that more tapes, a larger alphabet and bidirectionality do not give TMs more power in the sense that doing any of that would make more functions computable than by a TM with one unidirectional tape and alphabet $\{0,1\}$, nor does it put more functions into $P$. – G. Bach Aug 4 '14 at 2:46
• Here "unidirectional" means the tape is one-sided infinite I presume. Reading the first time I understood it meant it could move in only one direction. And yes, I think you are right: combining two symbols in a tape square you can efficiently simulate a two-sided tape. If you alternate (even and odd positions on the one sided tape represent negative and positive positions on the two sided tape) then the constant will be $2$ I guess. – Hendrik Jan Aug 4 '14 at 9:18