On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines

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 JVP-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.Introduction.We develop here some ideas for machines and computation over the real numbers R.One motivation for this comes from scientific computation.In this use of the computer, a reasonable idealization has the cost of multiplication independent of the size of the number.This contrasts with the usual theoretical computer science picture which takes into account the number of bits of the numbers.Another motivation is to bring the theory of computation into the domain of analysis, geometry and topology.The mathematics of these subjects can then be put to use in the systematic analysis of algorithms.On the other hand, there is an extensively developed subject of the theory of discrete computation, which we don't wish to lose in our theory.Toward this end we define machines, partial recursive functions, and other objects of study over a ring R. Then in the case where R is the ring of integers Z, we have the same objects (or perhaps equivalent objects) as the classical ones.Computable functions over Z are thus ordinary computable functions.R.E.sets over Z are ordinary R.E.sets.But when the ring is specialized to the real numbers, we have computable functions which are reasonable for the study of algorithms of numerical analysis.R.E.sets over R are no longer countable and include, for example, basins of attraction of complex analytic dynamical systems.

• Bulletin of the American Mathematical Society
  View PDF