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
- 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?)
- 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 \(\Sigma_2^0\) 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?
- 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 Bolzano-Weierstrass theorem is the jump of weak Kőnig's lemma
- The axiomatization of randomness
- 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
(24)- On the uniform computational content of the Baire category theorem
- Parallel and Serial Jumps of Weak Weak König’s Lemma
- Mathematical logic: proof theory, constructive mathematics. Abstracts from the workshop held November 8--14, 2020 (hybrid meeting)
- Cardinal invariants, non-lowness classes, and Weihrauch reducibility
- On notions of computability-theoretic reduction between Π21 principles
- Randomness notions and reverse mathematics
- Algebraic properties of the first-order part of a problem
- The Vitali Covering Theorem in the Weihrauch Lattice
- An inside/outside Ramsey theorem and recursion theory
- Connected choice and the Brouwer fixed point theorem
- Closed choice and a uniform low basis theorem
- Weihrauch goes Brouwerian
- scientific article; zbMATH DE number 2154080 (Why is no real title available?)
- scientific article; zbMATH DE number 7471680 (Why is no real title available?)
- Toward a generalized computability theory
- On the uniform computational content of computability theory
- A Galois connection between Turing jumps and limits
- The typical constructible object
- Completion of choice
- scientific article; zbMATH DE number 5064948 (Why is no real title available?)
- On the algebraic structure of Weihrauch degrees
- scientific article; zbMATH DE number 817189 (Why is no real title available?)
- On the uniform computational content of Ramsey's theorem
- Weihrauch Complexity in Computable Analysis
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)
