Publication Details
Title: On a Theory of Computation and Complexity Over the Real Numbers; NP Completeness, Recursive Functions and Universal Machines
Author: L. Blum, M. Shub, and S. Smale
Group: ICSI Technical Reports
Date: December 1988
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-88-012.pdf
Overview:
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 theory 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.
Bibliographic Information:
ICSI Technical Report TR-88-012
Bibliographic Reference:
L. Blum, M. Shub, and S. Smale. On a Theory of Computation and Complexity Over the Real Numbers; NP Completeness, Recursive Functions and Universal Machines. ICSI Technical Report TR-88-012, December 1988
Author: L. Blum, M. Shub, and S. Smale
Group: ICSI Technical Reports
Date: December 1988
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-88-012.pdf
Overview:
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 theory 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.
Bibliographic Information:
ICSI Technical Report TR-88-012
Bibliographic Reference:
L. Blum, M. Shub, and S. Smale. On a Theory of Computation and Complexity Over the Real Numbers; NP Completeness, Recursive Functions and Universal Machines. ICSI Technical Report TR-88-012, December 1988