Blum-Shub-Smale Computability Theory

(c) Dr. Christine Gassner Here, real numbers are considered as entities which may be operated (i.e. read, stored, output, added, subtracted, multiplied, and compared) exactly in one step each. Classical algorithms naturally pertaining to this paradigm include Gaussian Elimination, Dantzig's Simplex Method, and many more in algebraic geometry. This model generalizes the common Turing machine / integer RAM which operate similarly on the rings $\mathbb{F}_2=\{0,1\}$ and $\mathbb{Z}$, respectively, to the ring $\mathbb{R}$. In fact it turns out that traditional recursion theory largely carries over to the real case - although usually with very different proofs involving algebraic arguments. On the other hand, the equivalence of function computability and graph (semi-)decidability from the discrete case fails in this real model, as illustrated with the square root function. Also, other than in the discrete (and surprisingly the complex case), a decidable language may not admit running time bounds depending only on the length of the input. Finally the use of arbitrary real constants is under debate as it allows to decide arbitrary discrete problems.
Literature:
  • Blum, Cucker, Shub, Smale: Complexity and Real Computation, Springer-Verlag, (1998)
  • Felipe Cucker 1992: The arithmetical hierarchy over the reals
  • Cucker & Rossello: Recursiveness over the complex numbers is time-bounded 1993
  • Ziegler et al.: Kolmogorov Complexity over the Reals, 2008