On the uniform computational content of computability theory

DOI10.1007/S00224-017-9798-1zbMATH Open1420.03110arXiv1501.00433OpenAlexW3098669794MaRDI QIDQ1694010FDOQ1694010

Authors: Vasco Brattka, Matthew Hendtlass, Alexander P. Kreuzer 

Publication date: 1 February 2018

Published in: Theory of Computing Systems (Search for Journal in Brave)

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.

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

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

zbMATH Keywords

computable analysiscomputability theoryWeihrauch lattice

Mathematics Subject Classification ID

Algorithmic randomness and dimension (03D32) Computation over the reals, computable analysis (03D78) Recursively (computably) enumerable sets and degrees (03D25) Other Turing degree structures (03D28) First-order arithmetic and fragments (03F30)

Cites Work

• Algorithmic randomness and complexity.
• Topological properties of real number representations.
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Computability and Randomness
• ∏ 0 1 Classes and Degrees of Theories
• How incomputable is finding Nash equilibria?
• Classical recursion theory. Vol. II
• On the strength of Ramsey's theorem for pairs
• The cohesive principle and the Bolzano-Weierstraß principle
• A cohesive set which is not high
• Upward closure and cohesive degrees
• Weihrauch degrees, omniscience principles and weak computability
• Mass problems and measure-theoretic regularity
• Minimal degrees and the jump operator
• Diagonally non-computable functions and fireworks
• Comparing DNR and WWKL
• Computable invariance
• 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
• Borel Complexity of Topological Operations on Computable Metric Spaces
• The Bolzano-Weierstrass theorem is the jump of weak Kőnig's lemma
• Closed choice and a uniform low basis theorem
• On the strength of weak compactness
• How incomputable is the separable Hahn-Banach theorem?
• The axiomatization of randomness
• The upper semi-lattice of degrees of recursive unsolvability
• Diagonally non-computable functions and bi-immunity
• On uniform relationships between combinatorial problems
• A criterion for completeness of degrees of unsolvability
• Comparing the strength of diagonally nonrecursive functions in the absence of \(\Sigma_2^0\) induction
• Binary subtrees with few labeled paths
• Lowness for genericity
• The degree structure of Weihrauch-reducibility
• Degrees of unsolvability: a tutorial
• On the uniform computational content of computability theory
• Probabilistic computability and choice
• On the algebraic structure of Weihrauch degrees
• Inside the Muchnik degrees. II: The degree structures induced by the arithmetical hierarchy of countably continuous functions
• Las Vegas computability and algorithmic randomness
• Separating fragments of WLEM, LPO, and MP

Cited In (24)

• Completion of choice
• On the uniform computational content of Ramsey's theorem
• Closed choice and a uniform low basis theorem
• Title not available (Why is that?)
• Weihrauch goes Brouwerian
• Parallel and Serial Jumps of Weak Weak König’s Lemma
• Cardinal invariants, non-lowness classes, and Weihrauch reducibility
• Mathematical logic: proof theory, constructive mathematics. Abstracts from the workshop held November 8--14, 2020 (hybrid meeting)
• Algebraic properties of the first-order part of a problem
• On the uniform computational content of the Baire category theorem
• Randomness notions and reverse mathematics
• On notions of computability-theoretic reduction between Π21 principles
• The Vitali Covering Theorem in the Weihrauch Lattice
• The typical constructible object
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• An inside/outside Ramsey theorem and recursion theory
• Weihrauch Complexity in Computable Analysis
• Toward a generalized computability theory
• Connected choice and the Brouwer fixed point theorem
• On the uniform computational content of computability theory
• A Galois connection between Turing jumps and limits
• On the algebraic structure of Weihrauch degrees

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)