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 (50)

• Inside the Muchnik degrees. II: The degree structures induced by the arithmetical hierarchy of countably continuous functions
• Title not available (Why is that?)
• Completion of choice
• On the topological aspects of the theory of represented spaces
• Representations of Analytic Functions and Weihrauch Degrees
• Computability of Subsets of Metric Spaces
• Decomposing Borel functions using the Shore–Slaman join theorem
• Direct construction of Scott ideals
• De groot duality for represented spaces
• On the complexity of learning programs
• 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
• Computability on the Countable Ordinals and the Hausdorff-Kuratowski Theorem (Extended Abstract)
• 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
• 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
• Title not available (Why is that?)
• On the strength of marriage theorems and uniformity
• ON THE UNIFORM COMPUTATIONAL CONTENT OF RAMSEY’S THEOREM
• Reverse Mathematics of Matroids
• Reduction games, provability and compactness
• Title not available (Why is that?)
• Title not available (Why is that?)
• SEARCHING FOR AN ANALOGUE OF ATR₀ IN THE WEIHRAUCH LATTICE
• 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
• On the existence of a connected component of a graph
• Computability and Analysis, a Historical Approach
• On the algebraic structure of Weihrauch degrees
• Computable Stone spaces
• WEIHRAUCH GOES BROUWERIAN
• The Brouwer Fixed Point Theorem Revisited

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)