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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
17
$\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.)

Improve this answer
$\endgroup$
16
  • 1
    $\begingroup$ Thanks Yuval.Now I understand that RAM is faster than Turing machine.but why 2? $\endgroup$
    – Tanmoy Banerjee
    Commented 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$
    – Yuval Filmus
    Commented 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
    Commented 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
    Commented 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$
    – Yuval Filmus
    Commented 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.