5
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ There is no proof in the book? Have you tried working out how a TM would simulate a bidirectional TM? $\endgroup$
    – Raphael ♦
    Aug 3 '14 at 20:49
  • $\begingroup$ 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. $\endgroup$
    – G. Bach
    Aug 4 '14 at 2:45
  • 1
    $\begingroup$ 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$. $\endgroup$
    – G. Bach
    Aug 4 '14 at 2:46
  • $\begingroup$ 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. $\endgroup$
    – Hendrik Jan
    Aug 4 '14 at 9:18
1
$\begingroup$

In the book you mentioned above you simulate a infinitely long bidirectional TM increasing the number of symbols and by "“folding” it in an arbitrary location". Thus each cell in the unidirectional TM will represent 2 symbols or a pair. So this can be x/(symbol or blank), x/y or (symbol or blank)/x. Now T(n) is the worst case scenario. Let us assume that the current state of the TM is as follows

^ symbol for blank.

e/h|l/^|l/^|o/^|!/^|?/^ (this is equivalent to h|e|l|l|o|!|? in a bidirectional TM, basically bend on the first position itself). with head pointing to ?/^, now if I want to write to the position I have to write as a pair. But I cannot read the second symbol in the pair without iterating to the left most position and then to the right again. So from the head position ?/^ we have to iterate 6 times to the left and 5 times to the right to read "^". Once we read "^" we have to return, so iterate back so 6 times to the left and then 5 times to the right. Now that we know the second symbol in the pair, we can write the new symbol for ex . "u/^". In a more generalized sense to write something in a Tape in the above state we have iterate the length of the tape(n) 4 times. So it will take 4 times more time to halt on a regular TM in the worst case, so t(n) = 4t'(n).

Improve this answer
$\endgroup$
4
  • $\begingroup$ "Now T(n) is the worst case scenario" What does that mean? What is T? What is n? $\endgroup$
    – David Richerby
    May 14 '18 at 12:21
  • $\begingroup$ Definition 1.3 (Computing a function and running time) Let f : {0, 1}^∗ → {0, 1}^∗ and let T : N → N be some functions, and let M be a Turing machine. We say that M computes f if for every x ∈ {0, 1}^∗ , whenever M is initialized to the start configuration on input x, then it halts with f(x) written on its output tape. We say M computes f in T (n)-time if its computation on every input x requires at most T (|x|) steps. This is the definition given in the book he mentions above. $\endgroup$
    – Matthews jose
    May 14 '18 at 13:04
  • $\begingroup$ OK, but there are only 26 letters in the alphabet; 52 if you allow for upper and lower case. Although one book may define a letter to mean one particular thing, don't assume that this definition is universal and you can just write "T" and everyone will know what you mean. $\endgroup$
    – David Richerby
    May 14 '18 at 13:06
  • $\begingroup$ Yes yes sorry, this question was based on that book so I thought people reading this would have read the book and then the problem. $\endgroup$
    – Matthews jose
    May 14 '18 at 16:51

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.