On a Theory of Computation over the Real Numbers; NP Completeness, Recursive Functions and Universal Machines (Extended Abstract)
Lenore Blum, Mike Shub, Steve Smale · Foundations of Computer Science · 1988
We present a model for computation over an arbitrary (ordered) ring R. In this general setting, we obtain universal machines, partial recursive functions, as well as NP complete problems. While our theory reflects the classical over Z (e.g., the computable functions are the recursive functions) it also reflects the special mathematical character of the underlying ring R (e.g., complements of Julia sets provide natural examples of R.E. undecidable sets over the reals) and provides a natural setting for studying foundational issues concerning algorithms in numerical analysis.