4
$\begingroup$

There is a large body of literature on RAMs with "reasonable" and "unreasonable" operations, where "unreasonable" operations would yield a machine with too much power to be practically feasible.

For example, it is known that for integer RAMs, allowing unit-cost multiplication yields a machine that is exponentially faster than a Turing machine. In conjunction with Boolean operations, this would yield a machine that can solve PSPACE-complete problems in polynomial time. The situation gets worse if division or left shift are added. As a result, computational models allowing these sorts operations to be performed in constant time on arbitrarily large integers are typically considered to be "unreasonable" in that the resulting models are far too powerful to be practically feasible.

How does this situation generalize to real RAMs, where the registers are allowed to be real numbers?

One canonical model of real computation is the Blum-Shub-Smale machine, which can compute rational functions at unit cost.

Is this model "reasonable?" What other operations are allowable on a real RAM that would lead to reasonable/unreasonable behavior?

Improve this question
$\endgroup$
5
  • $\begingroup$ For your first question (is this reasonable?), can you define what you mean by reasonable? What research have you done? There's lots written on the subject; see en.wikipedia.org/wiki/Real_RAM (which already seems to answer your first question). It's certainly an interesting complexity class. Your second class is too broad; there are an unlimited (infinite) number of operations that one could add to the model. Can you edit the question to identify a focused, well-defined question? $\endgroup$
    – D.W. ♦
    Jul 3, 2017 at 1:13
  • $\begingroup$ The citation on that Wiki page is wrong - it cites Schonhage's paper on integer RAMs as somehow relating to real RAMs (which it obviously does not). I've been meaning to edit that for a bit now. As far as research is concerned, I've already talked about the research on integer RAMs where his exact topic is covered, I'm simply looking for the analogous concept for real RAMs. $\endgroup$
    – Mike Battaglia
    Jul 3, 2017 at 1:19
  • $\begingroup$ I can include links to integer RAM papers if need be, but I'm not sure it'd really be helpful (or necessary). As far as "reasonableness" is concerned, I'm simply looking to understand better which models wouldn't have an absurd degree of computational power to be practically feasible (as was the case with unit-cost multiplication for integer RAMs). $\endgroup$
    – Mike Battaglia
    Jul 3, 2017 at 1:22
  • $\begingroup$ OK, cool -- I didn't realize Wikipedia was wrong. Sounds like I'd recommend editing the question to focus on your first question, remove the second question, elaborate on what you mean by "reasonable", and mention that Wikipedia is wrong. $\endgroup$
    – D.W. ♦
    Jul 3, 2017 at 1:26
  • $\begingroup$ I left the second question, as I'm interested in knowing where the boundary between feasible and infeasible lies. It's hardly broad at all; the entire early literature on integer RAMs attempts to address this exact question, and I am simply restating it for real RAMs. $\endgroup$
    – Mike Battaglia
    Jul 4, 2017 at 20:14

0

Reset to default

Your Answer

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