Real hypercomputation and continuity

DOI10.1007/S00224-006-1343-6MaRDI QIDQ2642906zbMATH OpenOpenAlexFDO

Authors Martin Ziegler

Publication date 6 September 2007

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cs/0508069

zbMATH Keywords

discontinuous real functionsHeaviside functionmodels of real hypercomputationreal function computability

Mathematics Subject Classification ID

Turing machines and related notions (03D10) Hierarchies of computability and definability (03D55) Constructive and recursive analysis (03F60)

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.

Recommendations

• New Computational Paradigms
• Revising type-2 computation and degrees of discontinuity
• Some thoughts on hypercomputation
• Recursion theory on the reals and continuous-time computation
• Beyond recursive real functions

Cited in

(21)

• Recursion theory on the reals and continuous-time computation
• A topological view on algebraic computation models
• Probabilistic computability and choice
• Inside the Muchnik degrees. I: Discontinuity, learnability and constructivism
• Hartmanis-Stearns Conjecture on Real Time and Transcendence
• Computability on the countable ordinals and the Hausdorff-Kuratowski theorem (extended abstract)
• How constructive is constructing measures?
• Towards Computational Complexity Theory on Advanced Function Spaces in Analysis
• Computability of analytic functions with analytic machines
• Effective discontinuity and a characterisation of the superjump
• Fluctuations, effective learnability and metastability in analysis
• Closed choice and a uniform low basis theorem
• Real computation with least discrete advice: a complexity theory of nonuniform computability with applications to effective linear algebra
• A Galois connection between Turing jumps and limits
• A comparison of concepts from computable analysis and effective descriptive set theory
• Revising type-2 computation and degrees of discontinuity
• Weihrauch Complexity in Computable Analysis
• New Computational Paradigms
• On the topological aspects of the theory of represented spaces
• Representation theorems for analytic machines and computability of analytic functions
• The arithmetic hierarchy of real functions

This page was built for publication: Real hypercomputation and continuity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2642906)