Closed Choice and a Uniform Low Basis Theorem

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.

References in corpus (6)

• Effective Choice and Boundedness Principles in Computable Analysis
• Weihrauch Degrees, Omniscience Principles and Weak Computability
• Real Hypercomputation and Continuity
• On the (semi)lattices induced by continuous reducibilities
• Revising Type-2 Computation and Degrees of Discontinuity
• Infinite Oracle Queries in Type-2 Machines (Extended Abstract)

Cited by in corpus (46)

• The Bolzano-Weierstrass Theorem is the Jump of Weak König's Lemma
• On the algebraic structure of Weihrauch degrees
• Probabilistic Computability and Choice
• The degree structure of Weihrauch-reducibility
• Computational Problems in Metric Fixed Point Theory and their Weihrauch Degrees
• Computation with Advice
• Non-deterministic computation and the Jayne-Rogers Theorem
• A comparison of concepts from computable analysis and effective descriptive set theory
• Finite choice, convex choice and finding roots
• Connected Choice and the Brouwer Fixed Point Theorem
• On the Uniform Computational Content of Ramsey's Theorem
• Completion of Choice
• Computable Stone spaces
• On the Uniform Computational Content of Computability Theory
• On the existence of a connected component of a graph
• Finding descending sequences through ill-founded linear orders
• Weihrauch-completeness for layerwise computability
• Weihrauch goes Brouwerian
• Algebraic properties of the first-order part of a problem
• Many-one reductions and the category of multivalued functions
• A Galois connection between Turing jumps and limits
• On the Uniform Computational Content of the Baire Category Theorem
• Decomposing Borel functions using the Shore-Slaman join theorem
• Projection operators in the Weihrauch lattice
• The Vitali Covering Theorem in the Weihrauch Lattice
• Computability and Analysis, a Historical Approach
• Searching for an analogue of ATR in the Weihrauch lattice
• The open and clopen Ramsey theorems in the Weihrauch lattice
• Computability of the Radon-Nikodym derivative
• Inside the Muchnik Degrees I: Discontinuity, Learnability, and Constructivism
• Effective aspects of Hausdorff and Fourier dimension
• Computable analysis and notions of continuity in Coq
• Towards computable analysis on the generalised real line
• Stashing And Parallelization Pentagons
• The Weihrauch degree of finding Nash equilibria in multiplayer games
• Inside the Muchnik Degrees II: The Degree Structures induced by the Arithmetical Hierarchy of Countably Continuous Functions
• Relative Computability and Uniform Continuity of Relations
• Efficient Decomposition of Bimatrix Games (Extended Abstract)
• Closed Sets and Operators thereon: Representations, Computability and Complexity
• Function spaces for second-order polynomial time
• Computability of Initial Value Problems
• Universality, optimality, and randomness deficiency
• The Weihrauch lattice at the level of ${\mathbf{\Pi }}_1^1{-\mathsf{CA}}_0$: the Cantor-Bendixson theorem
• Some computability-theoretic reductions between principles around ${\mathsf{ATR}}_0$
• Indivisibility and uniform computational strength
• A jump operator on the Weihrauch degrees