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.

  • 1
    $\begingroup$ The RAM model doesn’t have any tapes. $\endgroup$ – Yuval Filmus Jun 14 '19 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 '19 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 '19 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 '19 at 15:36

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

  • 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 '19 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 '19 at 17:10

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.