Revising Type-2 Computation and Degrees of Discontinuity

Abstract

By the sometimes so-called MAIN THEOREM of Recursive Analysis, every computable real function is necessarily continuous. Weihrauch and Zheng (TCS'2000), Brattka (MLQ'2005), and Ziegler (ToCS'2006) have considered different relaxed notions of computability to cover also discontinuous functions. The present work compares and unifies these approaches. This is based on the concept of the JUMP of a representation: both a TTE-counterpart to the well known recursion-theoretic jump on Kleene's Arithmetical Hierarchy of hypercomputation: and a formalization of revising computation in the sense of Shoenfield. We also consider Markov and Banach/Mazur oracle-computation of discontinuous fu nctions and characterize the computational power of Type-2 nondeterminism to coincide with the first level of the Analytical Hierarchy.

to appear in Proc. CCA'06

References in corpus (1)

• Real Hypercomputation and Continuity

Cited by in corpus (13)

• Closed Choice and a Uniform Low Basis Theorem
• The Bolzano-Weierstrass Theorem is the Jump of Weak König's Lemma
• Probabilistic Computability and Choice
• Computation with Advice
• Non-deterministic computation and the Jayne-Rogers Theorem
• Towards Synthetic Descriptive Set Theory: An instantiation with represented spaces
• Infinite Oracle Queries in Type-2 Machines (Extended Abstract)
• On the topological aspects of the theory of represented spaces
• A Galois connection between Turing jumps and limits
• The descriptive theory of represented spaces
• A topological view on algebraic computation models
• Inside the Muchnik Degrees I: Discontinuity, Learnability, and Constructivism
• Computability on the space of countable ordinals