Let's consider two-head (and two tapes) Turing machine. Let some problem $P$ be decidable in $LOGSPACE$ on that machine. What about complexity of that problem on the normal Turing machine ( one head, one tape?)

I asked that question because I am thinking of some problem- I have to be able to get value of $i$-th cell but my input is read-only.

  • 2
    $\begingroup$ Space-bounded machines are always defined with one or more work tapes, which are read-write tapes, and the space bound only constrains them. Your input tape uses more than logarithmic space, but in return is read-only. $\endgroup$ – Yuval Filmus Apr 23 '17 at 9:54

Let T(n) be the time complexity of problem on two tapes Turing machine then time complexity on single tape Turing machine is going to $O(T(n)^2)$ (more precisely $10 \times T(n)^2$). You have mentioned that your problem is in $LOGSPACE$, So $T(n)$ will be going to be some polynomial in $n$. To simulate two tapes Turing machine by single tape encode locations 1,3,5,7... to encode the first tape and locations 2,4,6... to encode second tape and also use symbol for the encoding of head positions. Now to simulate the one movement of two tape Turing machine you need to first find the head position (swap left to right) so you need $O(T(n))$ steps. Now to simulate the $O(T(n)$ many steps you need $O(T(n)^2)$ time.

| cite | improve this answer | |

Your Answer

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