On the uniform computational content of computability theory
From MaRDI portal
Abstract: We demonstrate that the Weihrauch lattice can be used to classify the uniform computational content of computability-theoretic properties as well as the computational content of theorems in one common setting. The properties that we study include diagonal non-computability, hyperimmunity, complete consistent extensions of Peano arithmetic, 1-genericity, Martin-L"of randomness, and cohesiveness. The theorems that we include in our case study are the low basis theorem of Jockusch and Soare, the Kleene-Post theorem, and Friedberg's jump inversion theorem. It turns out that all the aforementioned properties and many theorems in computability theory, including all theorems that claim the existence of some Turing degree, have very little uniform computational content: they are located outside of the upper cone of binary choice (also known as LLPO); we call problems with this property indiscriminative. Since practically all theorems from classical analysis whose computational content has been classified are discriminative, our observation could yield an explanation for why theorems and results in computability theory typically have very few direct consequences in other disciplines such as analysis. A notable exception in our case study is the low basis theorem which is discriminative. This is perhaps why it is considered to be one of the most applicable theorems in computability theory. In some cases a bridge between the indiscriminative world and the discriminative world of classical mathematics can be established via a suitable residual operation and we demonstrate this in the case of the cohesiveness problem and the problem of consistent complete extensions of Peano arithmetic. Both turn out to be the quotient of two discriminative problems.
Recommendations
- Effective Choice and Boundedness Principles in Computable Analysis
- Effective choice and boundedness principles in computable analysis
- Weihrauch degrees, omniscience principles and weak computability
- On the uniform computational content of Ramsey's theorem
- Weihrauch degrees, omniscience principles and weak computability
Cites work
- A cohesive set which is not high
- A criterion for completeness of degrees of unsolvability
- Algorithmic randomness and complexity.
- Binary subtrees with few labeled paths
- Borel Complexity of Topological Operations on Computable Metric Spaces
- Classical recursion theory. Vol. II
- Closed choice and a uniform low basis theorem
- Comparing DNR and WWKL
- Comparing the strength of diagonally nonrecursive functions in the absence of _2⁰ induction
- Computability and Randomness
- Computability on subsets of metric spaces.
- Computable invariance
- Degrees of unsolvability: a tutorial
- Diagonally non-computable functions and bi-immunity
- Diagonally non-computable functions and fireworks
- Effective Borel measurability and reducibility of functions
- Effective Choice and Boundedness Principles in Computable Analysis
- How incomputable is finding Nash equilibria?
- How incomputable is the separable Hahn-Banach theorem?
- scientific article; zbMATH DE number 4070894 (Why is no real title available?)
- scientific article; zbMATH DE number 1955470 (Why is no real title available?)
- scientific article; zbMATH DE number 1460545 (Why is no real title available?)
- Inside the Muchnik degrees. II: The degree structures induced by the arithmetical hierarchy of countably continuous functions
- Las Vegas computability and algorithmic randomness
- Lowness for genericity
- Mass problems and measure-theoretic regularity
- Minimal degrees and the jump operator
- On the (semi)lattices induced by continuous reducibilities
- On the algebraic structure of Weihrauch degrees
- On the strength of Ramsey's theorem for pairs
- On the strength of weak compactness
- On the uniform computational content of computability theory
- On uniform relationships between combinatorial problems
- Probabilistic computability and choice
- Separating fragments of WLEM, LPO, and MP
- The axiomatization of randomness
- The Bolzano-Weierstrass theorem is the jump of weak Kőnig's lemma
- The cohesive principle and the Bolzano-Weierstraß principle
- The degree structure of Weihrauch-reducibility
- The upper semi-lattice of degrees of recursive unsolvability
- Topological properties of real number representations.
- Upward closure and cohesive degrees
- Weihrauch degrees, omniscience principles and weak computability
- ∏ 0 1 Classes and Degrees of Theories
Cited in
(31)- Toward a generalized computability theory
- On the uniform computational content of the Baire category theorem
- On the uniform computational content of computability theory
- Completion of choice
- Mathematical logic: proof theory, constructive mathematics. Abstracts from the workshop held November 8--14, 2020 (hybrid meeting)
- The Vitali Covering Theorem in the Weihrauch Lattice
- Parallel and Serial Jumps of Weak Weak König’s Lemma
- On notions of computability-theoretic reduction between Π21 principles
- The typical constructible object
- Closed choice and a uniform low basis theorem
- On the algebraic structure of Weihrauch degrees
- A Galois connection between Turing jumps and limits
- On the uniform computational content of Ramsey's theorem
- scientific article; zbMATH DE number 2154080 (Why is no real title available?)
- scientific article; zbMATH DE number 817189 (Why is no real title available?)
- Weihrauch Complexity in Computable Analysis
- Stashing and parallelization pentagons
- An inside/outside Ramsey theorem and recursion theory
- Randomness notions and reverse mathematics
- Cardinal invariants, non-lowness classes, and Weihrauch reducibility
- Connected choice and the Brouwer fixed point theorem
- scientific article; zbMATH DE number 5064948 (Why is no real title available?)
- Weihrauch goes Brouwerian
- Algebraic properties of the first-order part of a problem
- The Kleene-Post and Post's theorem in the calculus of inductive constructions
- On the Weihrauch degree of the additive Ramsey theorem
- Hilbert's tenth problem for term algebras with a substitution operator
- Complemented subsets and Boolean-valued, partial functions
- Defining long words succinctly in FO and MSO
- On the first-order parts of problems in the Weihrauch degrees
- Sequential discontinuity and first-order problems
This page was built for publication: On the uniform computational content of computability theory
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1694010)
