Characterizing the strongly jump-traceable sets via randomness

DOI10.1016/j.aim.2012.06.005zbMath1257.03068arXiv1109.6749OpenAlexW1970189970MaRDI 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

zbMATH Keywords

randomnessstrongly jump-traceable setssuperlowness

Mathematics Subject Classification ID

Constructive and recursive analysis (03F60) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Applications of computability and recursion theory (03D80) Recursively (computably) enumerable sets and degrees (03D25) Other degrees and reducibilities in computability and recursion theory (03D30) Algorithmic randomness and dimension (03D32)

Related Items (9)

Strong jump-traceability. II: \(K\)-triviality ⋮ STRONG JUMP-TRACEABILITY ⋮ Computing from projections of random points ⋮ Upper bounds on ideals in the computably enumerable Turing degrees ⋮ Demuth randomness and computational complexity ⋮ COARSE REDUCIBILITY AND ALGORITHMIC RANDOMNESS ⋮ Computably enumerable sets below random sets ⋮ On arithmetical level of the class of superhigh sets ⋮ Inherent enumerability of strong jump-traceability

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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

This page was built for publication: Characterizing the strongly jump-traceable sets via randomness