Randomness notions and partial relativization

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

Authors: George Barmpalias, Joseph S. Miller, André Nies 

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

reducibilitySchnorr randomnesshighnesslownessrelativisationweak randomnessMartin-Löf 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 (16)

• 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
• Randomness notions and reverse mathematics
• Relative randomness for Martin-Löf random sets
• On the interplay between effective notions of randomness and genericity
• Lowness for effective Hausdorff dimension
• Coherence of reducibilities with randomness notions
• Defining a randomness notion via another
• Unified characterizations of lowness properties via Kolmogorov complexity
• Uniform relativization
• Bad oracles in higher computability and randomness
• Demuth randomness and computational complexity
• Propagation of partial randomness

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)