×

Real hypercomputation and continuity. (English) Zbl 1122.03039

Summary: By the sometimes so-called Main Theorem of Recursive Analysis, every computable real function is necessarily continuous. We wonder whether and which kinds of hypercomputation allow for the effective evaluation of discontinuous \(f :\;{\mathbb R}\to{\mathbb R}\), too. More precisely the present work considers the following three super-Turing notions of real function computability:
relativized computation; specifically given oracle access to the Halting Problem \(\emptyset'\) or its jump \(\emptyset''\);
encoding input \(x\in{\mathbb R}\) and/or output \(y = f(x)\) in weaker ways also related to the Arithmetic Hierarchy;
nondeterministic computation.
It turns out that any \(f:{\mathbb R}\to{\mathbb 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.

MSC:

03D10 Turing machines and related notions
03D55 Hierarchies of computability and definability
03F60 Constructive and recursive analysis
68Q05 Models of computation (Turing machines, etc.) (MSC2010)

Citations:

Zbl 1115.03039