Computable Real Functions: Type 1 Computability Versus Type 2 Computability.
Peter H. Hertling · 1996
Based on the Turing machine model there are essentially two different notions of computable functions over the real numbers. The effective functions are defined only on computable real numbers and are Type 1 computable with respect to a numbering of the computable real numbers. The effectively continuous functions may be defined on arbitrary real nunbers. They are exactly those functions which are Type 2 computable with respect to an appropriate representation of the real numbers. We characterize the Type 2 computable functions on computable real numbers as exactly those Type 1 computable functions which satisfy a certain additional condition concerning their domain of definition. Our result is a sharp strengthening of the well-known continuity result of Tseitin and Moschovakis for effective functions. The result is presented for arbitrary computable metric spaces. 1 Introduction In this paper we compare two approaches for defining computability of functions between computable metric ...