2
$\begingroup$

In Turing Machine, we know that there's (fine-grained complexity) difference between one-tape, 2-taped and multi-taped TM, even though they could be simulated efficiently.

(Well, actually I'm not quite sure they are indeed seperated: i.e. $TIME(t)\neq TIME_{2-taped}(t)\neq TIME_{multi-taped}(t)$ )

But today I'd like to focus on RAM model, is there any complexity seperation between one-taped RAM model and multi-taped model? Though we might expect it be quite small because of random accessibility.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ The RAM model doesn’t have any tapes. $\endgroup$
    – Yuval Filmus
    Jun 14, 2019 at 8:05
  • $\begingroup$ It seems RAM model is to use a $log(n)$-bit index to access certain cell on a tape. $\endgroup$
    – Taylor Huang
    Jun 14, 2019 at 8:20
  • $\begingroup$ Having more than one “tape” gives you no advantage at all. That’s a nice exercise for you. $\endgroup$
    – Yuval Filmus
    Jun 14, 2019 at 8:29
  • $\begingroup$ I'm not sure about that. A "tape-manner" turing machine would require zigzagging to simulate its multi-taped version. In RAM model, it seems we still need zigzagging except that we only need log time to jump to that specific location. $\endgroup$
    – Taylor Huang
    Jun 14, 2019 at 15:36

1 Answer 1

Reset to default
3
$\begingroup$

Random-access machines support the following operation in constant time: $$ x \gets M[y], $$ where $M$ is the memory array, and $y$ is an index whose allowable size depends on the exact model. Whether $M$ is an array of bits or an array of words depends on your exact model.

If you had several different memory arrays, say $M_1[y],\ldots,M_r[y]$, then you could simulate the command $$ x \gets M_i[y] $$ with the command $$ x \gets M[ry + i] $$ which also takes constant time.

Therefore there is nothing to be gained by allowing several "memories".

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ The integer arithmetic you performed before memory access, i.e. $ry+i$, isn't that at least log time? $\endgroup$
    – Taylor Huang
    Jun 14, 2019 at 16:27
  • $\begingroup$ It depends on the model. In the unit cost RAM it will take unit time. You could also transform your program so that for each variable $y$, it also computes $ry+i$ for $i=1,\ldots,r$. The resulting overhead will be $O(r) = O(1)$. $\endgroup$
    – Yuval Filmus
    Jun 14, 2019 at 17:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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