Highness properties close to PA completeness
From MaRDI portal
Publication:2055279
DOI10.1007/s11856-021-2200-7zbMath1485.03164arXiv1912.03016OpenAlexW3199074435MaRDI QIDQ2055279
Joseph S. Miller, Noam Greenberg, André Nies
Publication date: 1 December 2021
Published in: Israel Journal of Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1912.03016
Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Algorithmic randomness and dimension (03D32)
Related Items (4)
Betwixt Turing and Kleene ⋮ Growth and irreducibility in path-incompressible trees ⋮ THE REVERSE MATHEMATICS OF THEOREMS OF JORDAN AND LEBESGUE ⋮ Randomness below complete theories of arithmetic
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Coherent randomness tests and computing the \(K\)-trivial sets
- Propagation of partial randomness
- Randomness and lowness notions via open covers
- Cone avoidance and randomness preservation
- Zufälligkeit und Wahrscheinlichkeit. Eine algorithmische Begründung der Wahrscheinlichkeitstheorie. (Randomness and probability. An algorithmic foundation of probability theory)
- On uniform relationships between combinatorial problems
- A Survey of Mučnik and Medvedev Degrees
- Turing Degrees and Muchnik Degrees of Recursively Bounded DNR Functions
- Kolmogorov complexity and the Recursion Theorem
- Algorithmic Randomness and Complexity
- Computability and Analysis, a Historical Approach
- Mass Problems and Randomness
- Randomness and differentiability
- Algorithmic Aspects of Lipschitz Functions
- Weihrauch Complexity in Computable Analysis
- The importance of Π10 classes in effective randomness
- Diagonally non-recursive functions and effective Hausdorff dimension
- Relativizations of randomness and genericity notions
- Cardinal invariants, non-lowness classes, and Weihrauch reducibility
- On the computability of perfect subsets of sets with positive measure
- Degrees of unsolvability of continuous functions
- DEEP CLASSES
- FORCING WITH BUSHY TREES
- Computability and Randomness
- Lowness for the Class of Schnorr Random Reals
- ∏ 0 1 Classes and Degrees of Theories
- Randomness, relativization and Turing degrees
This page was built for publication: Highness properties close to PA completeness
