The K-degrees, low for K degrees, and weakly low for K sets

DOI10.1215/00294527-2009-017MaRDI QIDQ987934zbMATH OpenOpenAlexFDO

Authors Joseph S. Miller

Publication date 2 September 2010

Published in Notre Dame Journal of Formal Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1215/00294527-2009-017

zbMATH Keywords

prefix-free Kolmogorov complexityMartin-Löf randomness

Mathematics Subject Classification ID

Algorithmic randomness and dimension (03D32) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Other degrees and reducibilities in computability and recursion theory (03D30)

Recommendations

• The Kolmogorov complexity of random reals
• Oscillation in the initial segment complexity of random reals
• Lowness properties and randomness
• Being low along a sequence and elsewhere
• Randomness, relativization and Turing degrees

Cited in

(27)

• Time-Bounded Kolmogorov Complexity and Solovay Functions
• A set with barely degree
• Characterizing strong randomness via Martin-Löf randomness
• Solovay functions and their applications in algorithmic randomness
• Chaitin's \(\Omega\) as a continuous function
• Reducibilities relating to Schnorr randomness
• Relating and contrasting plain and prefix Kolmogorov complexity
• Effectively approximating measurable sets by open sets
• Low upper bounds in the LR degrees
• Selection by recursively enumerable sets
• Analogues of Chaitin's Omega in the computably enumerable sets
• Randomness notions and partial relativization
• On the gap between trivial and nontrivial initial segment prefix-free complexity
• Lowness properties and randomness
• Low sets without subsets of higher many-one degree
• Initial segment complexities of randomness notions
• Time-bounded Kolmogorov complexity and Solovay functions
• Oreals with \(\Delta_2^0\)-bounded complexity and compressive power
• Cone avoidance and randomness preservation
• Being low along a sequence and elsewhere
• Randomness and initial segment complexity for measures
• Coherence of reducibilities with randomness notions
• scientific article; zbMATH DE number 1507242 (Why is no real title available?)
• Kolmogorov complexity of initial segments of sequences and arithmetical definability
• Oscillation in the initial segment complexity of random reals
• Prefix and plain Kolmogorov complexity characterizations of 2-randomness: simple proofs
• A Weakly 2-Random Set That Is Not Generalized Low

This page was built for publication: The \(K\)-degrees, low for \(K\) degrees, and weakly low for \(K\) sets

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