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.
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) |