Blum-Shub-Smale Computability Theory
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