Computability and Complexity with Inexact Real Arithmetic

Various models of computation with real arithmetic have been formulated and applied to the questions of what functions that use real numbers are computable, and how hard they are to compute. The major examples are the real RAM model and the recursion-theoretic model. Neither of these models incorporate the phenomenon of inexact real arithmetic, which occurs in programs that use fixed- or floating-point real arithmetic.

I'll briefly review the real RAM and recursion-theoretic models of real number computation, and describe a model called asymptotic computation that models inexact real arithmetic. I'll then give some results classifying what's computable in the asymptotic model, and how it compares to computability in the other two models. I'll also discuss complexity for the asymptotic model, and how it relates to the other two models.