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
- ∏ 0 1 Classes and Degrees of Theories
- 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?
- 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?)
- 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
Cited in
(62)- On the uniform computational content of the Baire category theorem
- Comparing representations for function spaces in computable analysis
- A topological view on algebraic computation models
- On the uniform computational content of computability theory
- Towards computable analysis on the generalised real line
- Automatic learning from positive data and negative counterexamples
- Completion of choice
- Finite choice, convex choice and sorting
- Probabilistic computability and choice
- Universality, optimality, and randomness deficiency
- Inside the Muchnik degrees. II: The degree structures induced by the arithmetical hierarchy of countably continuous functions
- Inside the Muchnik degrees. I: Discontinuity, learnability and constructivism
- On uniform relationships between combinatorial problems
- Effective choice and boundedness principles in computable analysis
- Computability on the countable ordinals and the Hausdorff-Kuratowski theorem (extended abstract)
- Reverse mathematics of matroids
- The Vitali Covering Theorem in the Weihrauch Lattice
- Many-one reductions and the category of multivalued functions
- scientific article; zbMATH DE number 426297 (Why is no real title available?)
- Computability and analysis, a historical approach
- The Brouwer fixed point theorem revisited
- On the existence of a connected component of a graph
- The Bolzano-Weierstrass theorem is the jump of weak Kőnig's lemma
- Real computation with least discrete advice: a complexity theory of nonuniform computability with applications to effective linear algebra
- On the algebraic structure of Weihrauch degrees
- A Galois connection between Turing jumps and limits
- A comparison of concepts from computable analysis and effective descriptive set theory
- On the uniform computational content of Ramsey's theorem
- Weihrauch-completeness for layerwise computability
- Decomposing Borel functions using the Shore-Slaman join theorem
- Computable analysis and notions of continuity in \textsc{Coq}
- THE OPEN AND CLOPEN RAMSEY THEOREMS IN THE WEIHRAUCH LATTICE
- A COMPARISON OF VARIOUS ANALYTIC CHOICE PRINCIPLES
- Computability of Subsets of Metric Spaces
- Weihrauch Complexity in Computable Analysis
- Stashing and parallelization pentagons
- Reduction games, provability and compactness
- Effective aspects of Hausdorff and Fourier dimension
- FINDING DESCENDING SEQUENCES THROUGH ILL-FOUNDED LINEAR ORDERS
- Connected choice and the Brouwer fixed point theorem
- Closed choice for finite and for convex sets
- On the strength of marriage theorems and uniformity
- Representations of analytic functions and Weihrauch degrees
- On the topological aspects of the theory of represented spaces
- Searching for an analogue of \(\text{ATR}_0\) in the Weihrauch lattice
- Weihrauch goes Brouwerian
- Algebraic properties of the first-order part of a problem
- Computable Stone spaces
- Notes on overt choice
- Direct construction of Scott ideals
- De groot duality for represented spaces
- On the complexity of learning programs
- COMPUTABLY COMPACT METRIC SPACES
- Computably and punctually universal spaces
- Computing measure as a primitive operation in real number computation
- Computably locally compact groups and their closed subgroups
- Computability of initial value problems
- Countable ordered groups and Weihrauch reducibility
- The Weihrauch lattice at the level of \(\boldsymbol{\Pi }^1_1{-}\mathsf{CA}_0\): the Cantor-Bendixson theorem
- Indivisibility and uniform computational strength
- On the Weihrauch degree of the additive Ramsey theorem
- Sequential discontinuity and first-order problems
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)
