Real Hypercomputation and Continuity
arXiv:cs/0508069 · doi:10.1007/s00224-006-1343-6
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 HYPERcomputation allow for the effective evaluation of also discontinuous f:R->R. 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 0' or its jump 0''; * encoding real input x and/or output y=f(x) in weaker ways also related to the Arithmetic Hierarchy; * non-deterministic 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 does provide the required power to evaluate for instance the discontinuous sign function.
previous version (extended abstract) has appeared in pp.562-571 of "Proc. 1st Conference on Computability in Europe" (CiE'05), Springer LNCS vol.3526
Cited by in corpus (20)
- Closed Choice and a Uniform Low Basis Theorem
- Computability and analysis: the legacy of Alan Turing
- Probabilistic Computability and Choice
- The degree structure of Weihrauch-reducibility
- Revising Type-2 Computation and Degrees of Discontinuity
- Non-deterministic computation and the Jayne-Rogers Theorem
- Computation with Advice
- A comparison of concepts from computable analysis and effective descriptive set theory
- Finite choice, convex choice and finding roots
- Towards Synthetic Descriptive Set Theory: An instantiation with represented spaces
- Infinite Oracle Queries in Type-2 Machines (Extended Abstract)
- A Galois connection between Turing jumps and limits
- The descriptive theory of represented spaces
- On the topological aspects of the theory of represented spaces
- How constructive is constructing measures?
- A topological view on algebraic computation models
- Inside the Muchnik Degrees I: Discontinuity, Learnability, and Constructivism
- Computability on the space of countable ordinals
- Real Analytic Machines and Degrees
- Randomized Computation of Continuous Data: Is Brownian Motion Computable?