0
$\begingroup$

This would be a computational model that would have unbounded space. But with a jump command that can access and do operations on any finite number of cells at once. Actual calculations would take time, but space could be accessed instantly. If it is not can it at-least solve some problems faster then a Turing machine?

$\endgroup$
3
  • $\begingroup$ I suspect you'll be interested in cs.stackexchange.com/q/22418/755 and cs.stackexchange.com/q/29062/755 and cstheory.stackexchange.com/q/36026/5038 and cs.stackexchange.com/q/2666/755. $\endgroup$
    – D.W.
    Jan 15 at 0:36
  • $\begingroup$ @D.W. thanks. One more question. On this model, would there be problems solvable in polynomial time with exponential space? As there is literally no slowdown from accessing memory and it could be freely accessed, and would ideally have some sort of command allowing it to switch to acting like a Turing machine for a bit. $\endgroup$ Jan 15 at 17:09
  • $\begingroup$ I believe that was answered here: cs.stackexchange.com/q/148404/755. For a Turing machine, the space needed is upper-bounded by the running time. In the RAM model, you can transform any polynomial-time algorithm into one that takes polynomial time and polynomial space. $\endgroup$
    – D.W.
    Jan 15 at 22:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.