patternCritical
why don't we use machines with random access memory as our basic model of computation?
Viewed 0 times
randomwhycomputationwithbasicmachinesmemoryusemodelaccess
Problem
Turing machines are perhaps the most popular model of computation for theoretical computer science. Turing machines don't have random access memory, since we can only do a read where the slider is currently located.
This seem unwieldy to me. Why don't theoretical computer scientists use a model with random access memory, like a register machine, as the basic model of computation?
This seem unwieldy to me. Why don't theoretical computer scientists use a model with random access memory, like a register machine, as the basic model of computation?
Solution
Why don't theoretical computer scientists use a model with random access memory, like a register machine, as the basic model of computation?
The short answer is that this model is actually more complicated to describe and prove things about. "Jumping" from one place in memory to another is a more complex operation. Note that it requires:
-
Reading an address (requires that we define how the address is written on the tape)
-
Jumping to where that address says on the tape
Alternatively I'm not sure what you have in mind by "register machine", but this also requires care. How large can the registers be? And the machine then has separate mechanisms for how it accesses/modifies the registers, and how it accesses/modifies main memory.
In sum, it's a more complicated model and Turing machines are easier to deal with.
However, the long answer is that theoretical computer scientists do use a model with random access memory, in real practice: it's called the RAM (Random Access Machine) model. The Turing machine is not considered to be a good model for so-called "fine-grained complexity" (e.g. whether a problem can be solved in $O(n^2)$ or $O(n)$ time), and so this requires more careful models. The RAM model is standard and perhaps, arguably, more accepted than the Turing machine as a model of how real computers work, despite being more complicated.
For example, we can show that for a Turing machine to decide if two strings are equal requires $O(n^2)$ time. But this of course does not hold in more accurate models of computation like the RAM model, where it will take $O(n)$. Therefore:
-
If you just care about whether a problem can be solved at all (or whether it can be solved in polynomial time), Turing machines are considered sufficient.
-
But if you care about exactly how difficult it is to solve, then you have to resort to a more complex model, such as RAMs.
The short answer is that this model is actually more complicated to describe and prove things about. "Jumping" from one place in memory to another is a more complex operation. Note that it requires:
-
Reading an address (requires that we define how the address is written on the tape)
-
Jumping to where that address says on the tape
Alternatively I'm not sure what you have in mind by "register machine", but this also requires care. How large can the registers be? And the machine then has separate mechanisms for how it accesses/modifies the registers, and how it accesses/modifies main memory.
In sum, it's a more complicated model and Turing machines are easier to deal with.
However, the long answer is that theoretical computer scientists do use a model with random access memory, in real practice: it's called the RAM (Random Access Machine) model. The Turing machine is not considered to be a good model for so-called "fine-grained complexity" (e.g. whether a problem can be solved in $O(n^2)$ or $O(n)$ time), and so this requires more careful models. The RAM model is standard and perhaps, arguably, more accepted than the Turing machine as a model of how real computers work, despite being more complicated.
For example, we can show that for a Turing machine to decide if two strings are equal requires $O(n^2)$ time. But this of course does not hold in more accurate models of computation like the RAM model, where it will take $O(n)$. Therefore:
-
If you just care about whether a problem can be solved at all (or whether it can be solved in polynomial time), Turing machines are considered sufficient.
-
But if you care about exactly how difficult it is to solve, then you have to resort to a more complex model, such as RAMs.
Context
StackExchange Computer Science Q#121354, answer score: 63
Revisions (0)
No revisions yet.