CHARACTERIZING LOWNESS FOR DEMUTH RANDOMNESS

DOI10.1017/jsl.2013.21zbMath1338.03080OpenAlexW1998457663MaRDI QIDQ2921009

Noam Greenberg, Dan Turetsky, André Nies, Laurent Bienvenu, Rodney G. Downey

Publication date: 30 September 2014

Published in: The Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1017/jsl.2013.21

zbMATH Keywords

lownessDemuth randomnesspartial relativization

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Recursively (computably) enumerable sets and degrees (03D25) Algorithmic randomness and dimension (03D32)

Related Items

Demuth’s Path to Randomness ⋮ STRONG JUMP-TRACEABILITY ⋮ A \(K\)-trivial set which is not jump traceable at certain orders ⋮ ON THE INTERPLAY BETWEEN EFFECTIVE NOTIONS OF RANDOMNESS AND GENERICITY ⋮ Lowness for bounded randomness ⋮ DEMUTH’S PATH TO RANDOMNESS ⋮ Inherent enumerability of strong jump-traceability

Cites Work

• Unnamed Item
• Demuth randomness and computational complexity
• Randomness and lowness notions via open covers
• On \(\Pi{}^ 0_ 1\) classes and their ranked points
• Pseudo-jump inversion, upper cone avoidance, and strong jump-traceability
• Lowness for difference tests
• Lowness properties and approximations of the jump
• Lowness properties and randomness
• Truth-table Schnorr randomness and truth-table reducible randomness
• On Schnorr and computable randomness, martingales, and machines
• MASS PROBLEMS AND HYPERARITHMETICITY
• Lowness for Kurtz randomness
• Every sequence is reducible to a random one
• Lowness for the class of random sets
• Lowness for the Class of Schnorr Random Reals
• The Degrees of Hyperimmune Sets

This page was built for publication: CHARACTERIZING LOWNESS FOR DEMUTH RANDOMNESS