1 Department of Computer Science, Faculty of Science, Aarhus University, Aarhus University
We present a new model for computability and complexity of real functions together with an implementation that it based on it. The model uses a two-layer approach in which low-type basic objects perform the computation of a real function, but, whenever needed, can be complemented with higher type characterizing functions. A similar discrimination is implemented in the presented real number package, which operates on both an approximation layer and a layer which operates on real numbers as complete entities. This approach allows the model to provide correctness and completeness to the established notions in computable analysis, while the efficiency of the implementation is not compromised by the need to create and maintain higher-type objects.
Computability and Complexity in Analysis 2003, 2003, p. 279-302