patternMinor
What motivates the RAM model?
Viewed 0 times
thewhatrammodelmotivates
Problem
It looks like most of today's algorithm analysis is done in models with constant-time random access, such as the word RAM model. I don't know much about physics but from popular sources I've heard that there's supposed to be a limit on information storage per volume and on information travel speed, so RAMs don't seem to be physically realizable. Modern computers have all these cache levels which I'd say makes them not very RAM-like. So why should theoretical algorithms be set in RAM?
Solution
Let me give a different take on it than vonbrand. Everything you said is true: the RAM model is not realistic for a number of reasons, and whereas it is possible to defend different aspects of it, such a defense doesn't really get to the heart of the matter.
The heart of the matter -- and the answer to your question -- is that the RAM model is the best thing we have. Compared to other models that are accepted, it more accurately models real-life computation. In particular, the reason we adopted the RAM model was primarily a response to Turing machines, as we found that the use of Turing machines leads to problems being artificially difficult to solve in terms of time complexity. The RAM model clearly solves this glaring issue, and thus it has been accepted, even though it remains far from perfect.
A classical example that illustrates the glaring issue with Turing machines is the problem of string equality: given input
$$ w_1 \# w_2$$
where $w_1, w_2$ are binary sequences and $\#$ is a separator, determining whether $w_1 = w_2$. It can be shown that any Turing machine for the equality problem takes $O(n^2)$ time. This is uncomfortable, because Turing machines are what everyone thinks of as the universal model of computation -- yet no software engineer or algorithms researcher believes that string equality really takes $O(n^2)$ time. So what gives? String equality should be linear, so we invent a new model where it is, and the best solution available right now is word RAM machines.
Perhaps some day in the future we will come up with a better model -- one that is simple, conceptually clear, and improves on RAM in its ability to model real-life computational complexity. For now, we can only make do with the best that we have.
The heart of the matter -- and the answer to your question -- is that the RAM model is the best thing we have. Compared to other models that are accepted, it more accurately models real-life computation. In particular, the reason we adopted the RAM model was primarily a response to Turing machines, as we found that the use of Turing machines leads to problems being artificially difficult to solve in terms of time complexity. The RAM model clearly solves this glaring issue, and thus it has been accepted, even though it remains far from perfect.
A classical example that illustrates the glaring issue with Turing machines is the problem of string equality: given input
$$ w_1 \# w_2$$
where $w_1, w_2$ are binary sequences and $\#$ is a separator, determining whether $w_1 = w_2$. It can be shown that any Turing machine for the equality problem takes $O(n^2)$ time. This is uncomfortable, because Turing machines are what everyone thinks of as the universal model of computation -- yet no software engineer or algorithms researcher believes that string equality really takes $O(n^2)$ time. So what gives? String equality should be linear, so we invent a new model where it is, and the best solution available right now is word RAM machines.
Perhaps some day in the future we will come up with a better model -- one that is simple, conceptually clear, and improves on RAM in its ability to model real-life computational complexity. For now, we can only make do with the best that we have.
Context
StackExchange Computer Science Q#129350, answer score: 5
Revisions (0)
No revisions yet.