On the uniform computational content of computability theory
From MaRDI portal
Publication:1694010
DOI10.1007/s00224-017-9798-1zbMath1420.03110arXiv1501.00433OpenAlexW3098669794MaRDI QIDQ1694010
Vasco Brattka, Matthew Hendtlass, Alexander P. Kreuzer
Publication date: 1 February 2018
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1501.00433
First-order arithmetic and fragments (03F30) Recursively (computably) enumerable sets and degrees (03D25) Other Turing degree structures (03D28) Algorithmic randomness and dimension (03D32) Computation over the reals, computable analysis (03D78)
Related Items
An inside/outside Ramsey theorem and recursion theory, On the uniform computational content of the Baire category theorem, On notions of computability-theoretic reduction between Π21 principles, The Typical Constructible Object, Algebraic properties of the first-order part of a problem, RANDOMNESS NOTIONS AND REVERSE MATHEMATICS, On the uniform computational content of computability theory, ON THE UNIFORM COMPUTATIONAL CONTENT OF RAMSEY’S THEOREM, The Vitali Covering Theorem in the Weihrauch Lattice, Parallel and Serial Jumps of Weak Weak König’s Lemma, Completion of choice, Unnamed Item, Mathematical logic: proof theory, constructive mathematics. Abstracts from the workshop held November 8--14, 2020 (hybrid meeting), On the algebraic structure of Weihrauch degrees, Unnamed Item, Connected choice and the Brouwer fixed point theorem, WEIHRAUCH GOES BROUWERIAN, Weihrauch Complexity in Computable Analysis
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The Bolzano-Weierstrass theorem is the jump of weak Kőnig's lemma
- Closed choice and a uniform low basis theorem
- Diagonally non-computable functions and fireworks
- Binary subtrees with few labeled paths
- Lowness for genericity
- How incomputable is the separable Hahn-Banach theorem?
- Computable invariance
- Classical recursion theory. Vol. II
- Upward closure and cohesive degrees
- Computability on subsets of metric spaces.
- Topological properties of real number representations.
- On the uniform computational content of computability theory
- Probabilistic computability and choice
- Inside the Muchnik degrees. II: The degree structures induced by the arithmetical hierarchy of countably continuous functions
- The upper semi-lattice of degrees of recursive unsolvability
- On the strength of Ramsey's theorem for pairs
- COMPARING THE STRENGTH OF DIAGONALLY NONRECURSIVE FUNCTIONS IN THE ABSENCE OF INDUCTION
- On uniform relationships between combinatorial problems
- Diagonally Non-Computable Functions and Bi-Immunity
- Las Vegas Computability and Algorithmic Randomness
- SEPARATING FRAGMENTS OF WLEM, LPO, AND MP
- The cohesive principle and the Bolzano-Weierstraß principle
- On the (semi)lattices induced by continuous reducibilities
- Weihrauch degrees, omniscience principles and weak computability
- Effective Choice and Boundedness Principles in Computable Analysis
- Computability of the Radon-Nikodym Derivative
- Effective Borel measurability and reducibility of functions
- Algorithmic Randomness and Complexity
- Degrees of Unsolvability: A Tutorial
- A criterion for completeness of degrees of unsolvability
- Borel Complexity of Topological Operations on Computable Metric Spaces
- Mass Problems and Measure-Theoretic Regularity
- Minimal degrees and the jump operator
- A cohesive set which is not high
- On the algebraic structure of Weihrauch degrees
- On the Strength of Weak Compactness
- The degree structure of Weihrauch-reducibility
- The axiomatization of randomness
- Comparing DNR and WWKL
- Computability and Randomness
- ∏ 0 1 Classes and Degrees of Theories