Levels of discontinuity, limit-computability, and jump operators
From MaRDI portal
(Redirected from Publication:4982344)
Other degrees and reducibilities in computability and recursion theory (03D30) Descriptive set theory (03E15) Constructive and recursive analysis (03F60) Categorical logic, topoi (03G30) Classification of real functions; Baire classification of sets and functions (26A21) Descriptive set theory (topological aspects of Borel, analytic, projective, etc. sets) (54H05)
Abstract: We develop a general theory of jump operators, which is intended to provide an abstraction of the notion of "limit-computability" on represented spaces. Jump operators also provide a framework with a strong categorical flavor for investigating degrees of discontinuity of functions and hierarchies of sets on represented spaces. We will provide a thorough investigation within this framework of a hierarchy of -measurable functions between arbitrary countably based -spaces, which captures the notion of computing with ordinal mind-change bounds. Our abstract approach not only raises new questions but also sheds new light on previous results. For example, we introduce a notion of "higher order" descriptive set theoretical objects, we generalize a recent characterization of the computability theoretic notion of "lowness" in terms of adjoint functors, and we show that our framework encompasses ordinal quantifications of the non-constructiveness of Hilbert's finite basis theorem.
Recommendations
- Inside the Muchnik degrees. I: Discontinuity, learnability and constructivism
- Revising type-2 computation and degrees of discontinuity
- A Galois connection between Turing jumps and limits
- \(\Sigma^{0}_\alpha\)-admissible representations. (Extended abstract)
- Three topological reducibilities for discontinuous functions
Cited in
(15)- A topological view on algebraic computation models
- Game characterizations and lower cones in the Weihrauch degrees
- Bounded jump and the high/low hierarchy
- Inside the Muchnik degrees. II: The degree structures induced by the arithmetical hierarchy of countably continuous functions
- Computability on the countable ordinals and the Hausdorff-Kuratowski theorem (extended abstract)
- Borel-piecewise continuous reducibility for uniformization problems
- A Galois connection between Turing jumps and limits
- A comparison of concepts from computable analysis and effective descriptive set theory
- Decomposing Borel functions using the Shore-Slaman join theorem
- Computability of Subsets of Metric Spaces
- Weihrauch Complexity in Computable Analysis
- Effective aspects of Hausdorff and Fourier dimension
- Game characterizations and lower cones in the Weihrauch degrees
- scientific article; zbMATH DE number 7093560 (Why is no real title available?)
- Notes on overt choice
This page was built for publication: Levels of discontinuity, limit-computability, and jump operators
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4982344)
