8
$\begingroup$

In algorithm analysis, we assume a generic one processor Random Access Machine (RAM). As far as I know, the RAM machine is no more efficient than the Turing machine. All algorithms can be implemented in the Turing machine. So my questions are:

  • If the Turing machine is as efficient as the RAM machine, then why are we not assuming Turing machine for algorithm analysis?

  • What is the difference between RAM and TM?

$\endgroup$
11
$\begingroup$

Turing machines are not as efficient as RAM machines. A RAM machine can access an arbitrary tape location in $O(1)$. A Turing machine can't. A RAM machine can do arithmetic in $O(1)$ (under certain restrictions). A Turing machine can't.

Turing machines polynomially simulate RAM machines, that is, for some constant $c$, any RAM machine running in time $O(n^k)$ can be simulated by a Turing machine running in time $O(n^{ck})$. (The constant is pretty reasonable, about $2$, depending on the Turing machine model.)

$\endgroup$
  • $\begingroup$ Thanks Yuval.Now I understand that RAM is faster than Turing machine.but why 2? $\endgroup$ – tanmoy Mar 9 '14 at 6:22
  • $\begingroup$ I get $2$ since that's (roughly) the time it naively takes to simulate random access. I could be wrong here. $\endgroup$ – Yuval Filmus Mar 9 '14 at 12:30
  • 1
    $\begingroup$ You should have a look at Cook's Time Bounded Random Access Machines, where the overhead in simulating one model with another is precisely proved. $\endgroup$ – Clément Jul 16 '14 at 0:07
  • $\begingroup$ Just a quick question: If a problem $\Pi$ has a polynomial-time algorithm on the RAM model, can I say that $\Pi$ has a polynomial-time algorithm on the TM model? Or alternatively, If a problem $\Pi$ has a polynomial-time algorithm on the RAM model, can I say that $\Pi$ is in P? $\endgroup$ – drzbir Dec 29 '16 at 19:35
  • 1
    $\begingroup$ @Azzo You are correct, a problem is in P iff it has a polynomial time algorithm in the RAM model iff it has a polynomial time algorithm in the Turing machine model. $\endgroup$ – Yuval Filmus Dec 29 '16 at 22:43

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.