0
$\begingroup$

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?

$\endgroup$

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.