On a Theory of Computation and Complexity Over the Real Numbers; NP Completeness, Recursive Functions and Universal Machines
| Title | On a Theory of Computation and Complexity Over the Real Numbers; NP Completeness, Recursive Functions and Universal Machines |
| Publication Type | Technical Report |
| Year of Publication | 1988 |
| Authors | Blum, L., Shub M., & Smale S. |
| Other Numbers | 498 |
| 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 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. |
| URL | http://www.icsi.berkeley.edu/pubs/techreports/tr-88-012.pdf |
| Bibliographic Notes | ICSI Technical Report TR-88-012 |
| Abbreviated Authors | L. Blum, M. Shub, and S. Smale |
| ICSI Publication Type | Technical Report |