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.

$\endgroup$
4
  • 1
    $\begingroup$ The RAM model doesn’t have any tapes. $\endgroup$ Commented 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$ Commented 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$ Commented 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$ Commented Jun 14, 2019 at 15:36

1 Answer 1

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".

$\endgroup$
2
  • 1
    $\begingroup$ The integer arithmetic you performed before memory access, i.e. $ry+i$, isn't that at least log time? $\endgroup$ Commented 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$ Commented Jun 14, 2019 at 17:10

Your Answer

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

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