Closed choice and a uniform low basis theorem
From MaRDI portal
(Redirected from Publication:424541)
Abstract: We study closed choice principles for different spaces. Given information about what does not constitute a solution, closed choice determines a solution. We show that with closed choice one can characterize several models of hypercomputation in a uniform framework using Weihrauch reducibility. The classes of functions which are reducible to closed choice of the singleton space, of the natural numbers, of Cantor space and of Baire space correspond to the class of computable functions, of functions computable with finitely many mind changes, of weakly computable functions and of effectively Borel measurable functions, respectively. We also prove that all these classes correspond to classes of non-deterministically computable functions with the respective spaces as advice spaces. Moreover, we prove that closed choice on Euclidean space can be considered as "locally compact choice" and it is obtained as product of closed choice on the natural numbers and on Cantor space. We also prove a Quotient Theorem for compact choice which shows that single-valued functions can be "divided" by compact choice in a certain sense. Another result is the Independent Choice Theorem, which provides a uniform proof that many choice principles are closed under composition. Finally, we also study the related class of low computable functions, which contains the class of weakly computable functions as well as the class of functions computable with finitely many mind changes. As one main result we prove a uniform version of the Low Basis Theorem that states that closed choice on Cantor space (and the Euclidean space) is low computable. We close with some related observations on the Turing jump operation and its initial topology.
Recommendations
Cites work
- scientific article; zbMATH DE number 4068853 (Why is no real title available?)
- scientific article; zbMATH DE number 722611 (Why is no real title available?)
- scientific article; zbMATH DE number 1460545 (Why is no real title available?)
- scientific article; zbMATH DE number 3073037 (Why is no real title available?)
- A blend of methods of recursion theory and topology.
- Borel Complexity of Topological Operations on Computable Metric Spaces
- Classical recursion theory. The theory of functions and sets of natural numbers
- Classical recursion theory. Vol. II
- Computability and randomness
- Computability on subsets of metric spaces.
- Computational complexity on computable metric spaces
- Descriptive set theory
- Effective Borel measurability and reducibility of functions
- Effective Choice and Boundedness Principles in Computable Analysis
- Hierarchies of Δ02‐measurable k ‐partitions
- How incomputable is finding Nash equilibria?
- How incomputable is the separable Hahn-Banach theorem?
- Mind change complexity of inferring unbounded unions of restricted pattern languages from positive data
- Notions of Probabilistic Computability on Represented Spaces
- On degrees of recursive unsolvability
- On the (semi)lattices induced by continuous reducibilities
- Plottable Real Number Functions and the Computable Graph Theorem
- Real hypercomputation and continuity
- Revising type-2 computation and degrees of discontinuity
- Topological properties of concept spaces (full version)
- Undecidability in Weihrauch degrees
- Weihrauch degrees, omniscience principles and weak computability
- ∏ 0 1 Classes and Degrees of Theories
Cited in
(52)- Inside the Muchnik degrees. II: The degree structures induced by the arithmetical hierarchy of countably continuous functions
- Searching for an analogue of \(\text{ATR}_0\) in the Weihrauch lattice
- Completion of choice
- On the uniform computational content of Ramsey's theorem
- Closed choice for finite and for convex sets
- On the topological aspects of the theory of represented spaces
- Computability of Subsets of Metric Spaces
- Computable analysis and notions of continuity in \textsc{Coq}
- Notes on overt choice
- Direct construction of Scott ideals
- De groot duality for represented spaces
- On the complexity of learning programs
- Weihrauch goes Brouwerian
- Towards computable analysis on the generalised real line
- Real computation with least discrete advice: a complexity theory of nonuniform computability with applications to effective linear algebra
- Effective choice and boundedness principles in computable analysis
- FINDING DESCENDING SEQUENCES THROUGH ILL-FOUNDED LINEAR ORDERS
- Algebraic properties of the first-order part of a problem
- The Bolzano-Weierstrass theorem is the jump of weak Kőnig's lemma
- On the uniform computational content of the Baire category theorem
- Comparing representations for function spaces in computable analysis
- On uniform relationships between combinatorial problems
- COMPUTABLY COMPACT METRIC SPACES
- THE OPEN AND CLOPEN RAMSEY THEOREMS IN THE WEIHRAUCH LATTICE
- Reverse mathematics of matroids
- Representations of analytic functions and Weihrauch degrees
- Weihrauch-completeness for layerwise computability
- The Vitali Covering Theorem in the Weihrauch Lattice
- Universality, optimality, and randomness deficiency
- A topological view on algebraic computation models
- Many-one reductions and the category of multivalued functions
- Computably and punctually universal spaces
- Probabilistic computability and choice
- Inside the Muchnik degrees. I: Discontinuity, learnability and constructivism
- A comparison of concepts from computable analysis and effective descriptive set theory
- Decomposing Borel functions using the Shore-Slaman join theorem
- Computability and analysis, a historical approach
- scientific article; zbMATH DE number 7471680 (Why is no real title available?)
- On the strength of marriage theorems and uniformity
- Reduction games, provability and compactness
- scientific article; zbMATH DE number 426297 (Why is no real title available?)
- The Brouwer fixed point theorem revisited
- Weihrauch Complexity in Computable Analysis
- Automatic learning from positive data and negative counterexamples
- Connected choice and the Brouwer fixed point theorem
- Effective aspects of Hausdorff and Fourier dimension
- On the uniform computational content of computability theory
- A Galois connection between Turing jumps and limits
- On the existence of a connected component of a graph
- On the algebraic structure of Weihrauch degrees
- Computable Stone spaces
- Computability on the countable ordinals and the Hausdorff-Kuratowski theorem (extended abstract)
This page was built for publication: Closed choice and a uniform low basis theorem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q424541)
