16
$\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$

1 Answer 1

16
$\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$
16
  • 1
    $\begingroup$ Thanks Yuval.Now I understand that RAM is faster than Turing machine.but why 2? $\endgroup$ Mar 9, 2014 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$ Mar 9, 2014 at 12:30
  • 2
    $\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, 2014 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, 2016 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$ Dec 29, 2016 at 22:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.