# One-taped RAM vs Multi-taped RAM

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.

• The RAM model doesn’t have any tapes. – Yuval Filmus Jun 14 '19 at 8:05
• It seems RAM model is to use a $log(n)$-bit index to access certain cell on a tape. – Taylor Huang Jun 14 '19 at 8:20
• Having more than one “tape” gives you no advantage at all. That’s a nice exercise for you. – Yuval Filmus Jun 14 '19 at 8:29
• 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. – 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.
• The integer arithmetic you performed before memory access, i.e. $ry+i$, isn't that at least log time? – Taylor Huang Jun 14 '19 at 16:27
• 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)$. – Yuval Filmus Jun 14 '19 at 17:10