Characterizing the strongly jump-traceable sets via randomness
From MaRDI portal
Publication:456804
DOI10.1016/j.aim.2012.06.005zbMath1257.03068arXiv1109.6749MaRDI QIDQ456804
Denis R. Hirschfeldt, André Nies, Noam Greenberg
Publication date: 16 October 2012
Published in: Advances in Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1109.6749
03F60: Constructive and recursive analysis
68Q30: Algorithmic information theory (Kolmogorov complexity, etc.)
03D80: Applications of computability and recursion theory
03D25: Recursively (computably) enumerable sets and degrees
03D30: Other degrees and reducibilities in computability and recursion theory
03D32: Algorithmic randomness and dimension
Related Items
STRONG JUMP-TRACEABILITY, Computing from projections of random points, Inherent enumerability of strong jump-traceability, Strong jump-traceability. II: \(K\)-triviality, Computably enumerable sets below random sets, On arithmetical level of the class of superhigh sets, Upper bounds on ideals in the computably enumerable Turing degrees, Demuth randomness and computational complexity, COARSE REDUCIBILITY AND ALGORITHMIC RANDOMNESS
Cites Work
- Strong jump-traceability. II: \(K\)-triviality
- Computably enumerable sets below random sets
- Demuth randomness and computational complexity
- On strongly jump traceable reals
- Superhighness
- Strong jump-traceability. I: The computably enumerable case
- Lowness properties and approximations of the jump
- Lowness properties and randomness
- A random set which only computes strongly jump-traceable c.e. sets
- A Refinement of Lown and Highn for the R.E. Degrees
- Benign cost functions and lowness properties
- Kolmogorov complexity and the Recursion Theorem
- Algorithmic Randomness and Complexity
- Randomness and Computability: Open Questions
- Calibrating Randomness
- MASS PROBLEMS AND HYPERARITHMETICITY
- 𝐾-trivial degrees and the jump-traceability hierarchy
- Superhighness and Strong Jump Traceability
- Every sequence is reducible to a random one
- A Theory of Program Size Formally Identical to Information Theory
- Lowness for the class of random sets
- The axiomatization of randomness
- Almost everywhere domination and superhighness
- Using random sets as oracles
- Computability and Randomness
- Strong jump-traceability and Demuth randomness
- Inherent enumerability of strong jump-traceability
- ∏ 0 1 Classes and Degrees of Theories
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
