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?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.