Randomness notions and partial relativization

DOI10.1007/s11856-012-0012-5zbMath1279.03065OpenAlexW2090776193MaRDI 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

reducibilityhighnesslownessMartin-Löf randomnessSchnorr randomnessrelativisationweak randomness

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Algorithmic randomness and dimension (03D32)

Related Items (6)

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

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

This page was built for publication: Randomness notions and partial relativization