On a theory of computation over the real numbers; NP completeness, recursive functions and universal machines
- 1 January 1988
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 387-397
- https://doi.org/10.1109/sfcs.1988.21955
Abstract
A model for computation over an arbitrary (ordered) ring R is presented. In this general setting, universal machines, partial recursive functions, and NP-complete problems are obtained. While the theory reflects of 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 recursively enumerable undecidable sets over the reals) and provides a natural setting for studying foundational issues concerning algorithms in numerical analysis.Keywords
This publication has 30 references indexed in Scilit:
- Complexity theory on real numbers and functionsPublished by Springer Nature ,2005
- Alfred Tarski's elimination theory for real closed fieldsThe Journal of Symbolic Logic, 1988
- On the real spectrum of a ring and its application to semialgebraic geometryBulletin of the American Mathematical Society, 1986
- Arithmetic on curvesBulletin of the American Mathematical Society, 1986
- Register machine proof of the theorem on exponential diophantine representation of enumerable setsThe Journal of Symbolic Logic, 1984
- Complex analytic dynamics on the Riemann sphereBulletin of the American Mathematical Society, 1984
- Computability and noncomputability in classical analysisTransactions of the American Mathematical Society, 1983
- Lower bounds for algebraic decision treesJournal of Algorithms, 1982
- The Diophantine problem for polynomial rings and fields of rational functionsTransactions of the American Mathematical Society, 1978
- Proving simultaneous positivity of linear formsJournal of Computer and System Sciences, 1972