The \(K\)-degrees, low for \(K\) degrees, and weakly low for \(K\) sets
From MaRDI portal
Publication:987934
DOI10.1215/00294527-2009-017zbMath1213.03053OpenAlexW2049660564MaRDI QIDQ987934
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
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