Randomness notions and partial relativization

DOI10.1007/S11856-012-0012-5zbMATH Open1279.03065OpenAlexW2090776193MaRDI QIDQ375818FDOQ375818

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

Recommendations

• scientific article; zbMATH DE number 1531917
• Lowness for the class of random sets
• Relative randomness for Martin-Löf random sets
• Relativizations of randomness and genericity notions
• Coherence of reducibilities with randomness notions

zbMATH Keywords

[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=Martin-L%EF%BF%BD%EF%BF%BDf+randomness&go=Go Martin-L��f randomness]reducibilitySchnorr randomnesshighnesslownessrelativisationweak randomness

Mathematics Subject Classification ID

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

Cites Work

• Lowness properties and randomness
• Computational randomness and lowness
• Lowness notions, measure and domination
• The \(K\)-degrees, low for \(K\) degrees, and weakly low for \(K\) sets
• Counting the Changes of Random ${\Delta^0_2}$ Sets
• MASS PROBLEMS AND HYPERARITHMETICITY
• Information-theoretic characterizations of recursive infinite strings
• Randomness, lowness and degrees
• Lowness for Kurtz randomness
• Title not available (Why is that?)
• 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
• Demuth randomness and computational complexity
• \(\Pi_1^0 \) classes, LR degrees and Turing degrees
• Relative randomness and cardinality

Cited In (8)

• Relative randomness and cardinality
• Title not available (Why is that?)
• Computing from projections of random points
• Characterizing strong randomness via Martin-Löf randomness
• JSL volume 79 issue 2 Cover and Front matter
• Lowness for effective Hausdorff dimension
• Defining a randomness notion via another
• Demuth randomness and computational complexity

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q375818)