Real hypercomputation and continuity

Abstract

By the sometimes so-called Main Theorem of Recursive Analysis, every computable real function is necessarily continuous. We wonder whether and which kinds of hype rcomputation allow for the effective evaluation of also discontinuous f: R ->-> R. More precisely the present work considers the following three superTuring notions of real function computability:

- lativized computation; specifically given oracle access to the Halting Problem 0' or its jump 0";

- encoding input x epsilon R and/or output y = f (x) in weaker ways also related to the Arithmetic Hierarchy;

- nondeterministic computation.

It turns out that any f: R ->-> R computable in the first or second sense is still necessarily continuous whereas the third type of hypercomputation provides the required power to evaluate for instance the discontinuous Heaviside function.