Randomness notions and partial relativization

DOI10.1007/s11856-012-0012-5zbMath1279.03065MaRDI QIDQ375818

André Nies, Joseph S. Miller, George Barmpalias

Publication date: 1 November 2013

Published in: Israel Journal of Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11856-012-0012-5

zbMATH Keywords

reducibility; highness; lowness; Martin-Löf randomness; Schnorr randomness; relativisation; weak randomness

Mathematics Subject Classification ID

68Q30: Algorithmic information theory (Kolmogorov complexity, etc.)

03D32: Algorithmic randomness and dimension

Related Items

Computing from projections of random points, Lowness for effective Hausdorff dimension, Characterizing strong randomness via Martin-Löf randomness, Demuth randomness and computational complexity, Defining a randomness notion via another, JSL volume 79 issue 2 Cover and Front matter

Cites Work

• Unnamed Item
• Demuth randomness and computational complexity
• \(\Pi_1^0 \) classes, LR degrees and Turing degrees
• Relative randomness and cardinality
• The \(K\)-degrees, low for \(K\) degrees, and weakly low for \(K\) sets
• Information-theoretic characterizations of recursive infinite strings
• Lowness properties and randomness
• Computational randomness and lowness
• Lowness notions, measure and domination
• Randomness, lowness and degrees
• MASS PROBLEMS AND HYPERARITHMETICITY
• Counting the Changes of Random ${\Delta^0_2}$ Sets
• Lowness for Kurtz randomness
• Lowness for the class of random sets
• Almost everywhere domination and superhighness
• Low for random reals and positive-measure domination
• Almost everywhere domination
• A Weakly 2-Random Set That Is Not Generalized Low