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?
Real RAMs with reasonable operations
complexity theory;computation models;real numbers