Computability and Continuity of Real Number Functions

Peter Hertling

(University of Hagen, Germany)

In contrast to computations over discrete structures, for computations over the real numbers topological notions play an important role. While some approaches for defining computable real functions incorporate continuity in an obvious way, others imply continuity rather surprisingly. We present several results about the relationship between computability and continuity, starting with the continuity of Banach--Mazur computable functions. The main result presented will be a strengthening of results by Kreisel, Lacombe, Shoenfield, by Tseitin, by Moschovakis, and by Berger. We will characterize the effectively continuous functions on the computable elements of certain topological spaces as those functions which are effective with respect to a Goedel numbering of the computable elements and which have a sufficiently nice domain of definition.
Thursday 21st September 2000, 14:00
Robert Recorde Room
Department of Computer Science