The \(K\)-degrees, low for \(K\) degrees, and weakly low for \(K\) sets

DOI10.1215/00294527-2009-017zbMath1213.03053OpenAlexW2049660564MaRDI QIDQ987934

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

Martin-Löf randomnessprefix-free Kolmogorov complexity

Mathematics Subject Classification ID

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

Related Items

Reducibilities relating to Schnorr randomness ⋮ Relating and contrasting plain and prefix Kolmogorov complexity ⋮ Initial segment complexities of randomness notions ⋮ Time-Bounded Kolmogorov Complexity and Solovay Functions ⋮ Randomness notions and partial relativization ⋮ Characterizing strong randomness via Martin-Löf randomness ⋮ Low upper bounds in the LR degrees ⋮ CHAITIN’S Ω AS A CONTINUOUS FUNCTION ⋮ Effectively approximating measurable sets by open sets ⋮ Time-bounded Kolmogorov complexity and Solovay functions ⋮ On the gap between trivial and nontrivial initial segment prefix-free complexity ⋮ Oscillation in the initial segment complexity of random reals ⋮ ON REALS WITH -BOUNDED COMPLEXITY AND COMPRESSIVE POWER ⋮ Solovay functions and their applications in algorithmic randomness ⋮ Prefix and plain Kolmogorov complexity characterizations of 2-randomness: simple proofs ⋮ Selection by Recursively Enumerable Sets ⋮ Kolmogorov complexity of initial segments of sequences and arithmetical definability ⋮ Coherence of reducibilities with randomness notions ⋮ BEING LOW ALONG A SEQUENCE AND ELSEWHERE ⋮ Randomness and initial segment complexity for measures ⋮ Cone avoidance and randomness preservation

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