# RAM and Turing machines: time complexity of simulation

My RAM machine is very simple:

• it has $$k$$ tapes, an input tape and one special control tape

• it has an infinite memory (array called $$A$$) which can be accessed randomly

• the control tape is read anytime the machine enters the special $$q_{control}$$ state

• the control tape always contains the symbol $$R$$ or $$W$$ specifying the memory operation (read or write) and a binary number representing the address of the cell in $$A$$

• in case of $$W$$ the machine also needs to have a symbol of the alphabet on the control tape to be saved into the chosen cell of $$A$$

• in case of $$R$$ the machine puts whatever it has read onto the control tape again

• other than that it is very similar to a Turing machine ($$k$$ work tapes, states)

I would like to show that this computation can be simulated on a Turing machine with at most quadratic overhead. (If function $$f$$ is computable on RAM in $$T(n)$$, it is computable on the Turing machine in $$T(n)^2$$.

My approach is to use the fact that the RAM machine can use at most $$T(n)$$ cells in $$A$$. I could transform it into a tape of the Turing machine which would be processed sequentially for each "control" call of the RAM machine. This would naturally lead to $$T(n)^2$$ time complexity.

However, I would also need a tape to map "RAM addresses" to the corresponding addresses (position) on my fake-memory tape. How else would I remember where I have saved the symbol corresponding to the address "11010101" when it needs to be read? But the catch is: the address can be at most $$T(n)$$ long, which takes us immediately to the $$T(n)^3$$ time complexity.

How to solve it?