About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Bulletin of the American Mathematical Society
Paper
On a theory of computation and complexity over the real numbers: Np-completeness, recursive functions and universal machines
Abstract
We present a model for computation over the reals or 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. © 1989 American Mathematical Society.