Closed choice and a uniform low basis theorem

DOI10.1016/J.APAL.2011.12.020zbMATH Open1251.03082arXiv1002.2800OpenAlexW2044009111MaRDI QIDQ424541FDOQ424541

Authors: Vasco Brattka, Matthew De Brecht, Arno Pauly 

Publication date: 1 June 2012

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1002.2800

Recommendations

• Effective Choice and Boundedness Principles in Computable Analysis
• Effective choice and boundedness principles in computable analysis
• Completion of choice
• On the uniform computational content of computability theory
• Weihrauch degrees, omniscience principles and weak computability

zbMATH Keywords

computable analysiscomputable functionsBorel complexityclosed choice principlesmodels of hypercomputationWeihrauch reducibility

Mathematics Subject Classification ID

Descriptive set theory (03E15) Axiom of choice and related propositions (03E25) Other degrees and reducibilities in computability and recursion theory (03D30) Constructive and recursive analysis (03F60)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Computability and randomness
• Title not available (Why is that?)
• Descriptive set theory
• ∏ 0 1 Classes and Degrees of Theories
• Classical recursion theory. The theory of functions and sets of natural numbers
• How incomputable is finding Nash equilibria?
• Classical recursion theory. Vol. II
• Mind change complexity of inferring unbounded unions of restricted pattern languages from positive data
• Topological properties of concept spaces (full version)
• Weihrauch degrees, omniscience principles and weak computability
• Real hypercomputation and continuity
• Computability on subsets of metric spaces.
• On the (semi)lattices induced by continuous reducibilities
• Effective Choice and Boundedness Principles in Computable Analysis
• Effective Borel measurability and reducibility of functions
• Undecidability in Weihrauch degrees
• Borel Complexity of Topological Operations on Computable Metric Spaces
• Computational complexity on computable metric spaces
• Revising type-2 computation and degrees of discontinuity
• How incomputable is the separable Hahn-Banach theorem?
• A blend of methods of recursion theory and topology.
• Plottable Real Number Functions and the Computable Graph Theorem
• Title not available (Why is that?)
• Notions of Probabilistic Computability on Represented Spaces
• Hierarchies of Δ⁰₂‐measurable k ‐partitions
• On degrees of recursive unsolvability

Cited In (53)

• Computably and punctually universal spaces
• Searching for an analogue of \(\text{ATR}_0\) in the Weihrauch lattice
• Inside the Muchnik degrees. II: The degree structures induced by the arithmetical hierarchy of countably continuous functions
• 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
• 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
• Effective choice and boundedness principles in computable analysis
• Real computation with least discrete advice: a complexity theory of nonuniform computability with applications to effective linear algebra
• Algebraic properties of the first-order part of a problem
• FINDING DESCENDING SEQUENCES THROUGH ILL-FOUNDED LINEAR ORDERS
• COMPUTABLY COMPACT METRIC SPACES
• On uniform relationships between combinatorial problems
• On the uniform computational content of the Baire category theorem
• Comparing representations for function spaces in computable analysis
• The Bolzano-Weierstrass theorem is the jump of weak Kőnig's lemma
• THE OPEN AND CLOPEN RAMSEY THEOREMS IN THE WEIHRAUCH LATTICE
• Representations of analytic functions and Weihrauch degrees
• Reverse mathematics of matroids
• 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
• 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
• Title not available (Why is that?)
• Computability and analysis, a historical approach
• On the strength of marriage theorems and uniformity
• Reduction games, provability and compactness
• Title not available (Why is that?)
• The Brouwer fixed point theorem revisited
• Title not available (Why is that?)
• 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
• Computability of the Radon-Nikodym derivative
• 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)