Kolmogorov Complexity and Solovay Functions

DOI10.4230/LIPIcs.STACS.2009.1810zbMath1236.68108arXiv0902.1041OpenAlexW2962873506MaRDI QIDQ5389973

Laurent Bienvenu, Rodney G. Downey

Publication date: 24 April 2012

Full work available at URL: https://arxiv.org/abs/0902.1041

zbMATH Keywords

Kolmogorov complexityalgorithmic randomnessK-triviality

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Related Items (14)

Random Semicomputable Reals Revisited ⋮ Randomness, Computation and Mathematics ⋮ Time-Bounded Kolmogorov Complexity and Solovay Functions ⋮ Strong jump-traceability. II: \(K\)-triviality ⋮ CHAITIN’S Ω AS A CONTINUOUS FUNCTION ⋮ Time-bounded Kolmogorov complexity and Solovay functions ⋮ Solovay functions and their applications in algorithmic randomness ⋮ Randomness for computable measures and initial segment complexity ⋮ Kolmogorov complexity of initial segments of sequences and arithmetical definability ⋮ Coherence of reducibilities with randomness notions ⋮ Optimal asymptotic bounds on the oracle use in computations from Chaitin's Omega ⋮ BEING LOW ALONG A SEQUENCE AND ELSEWHERE ⋮ $K$-triviality in computable metric spaces ⋮ SOME QUESTIONS OF UNIFORMITY IN ALGORITHMIC RANDOMNESS

This page was built for publication: Kolmogorov Complexity and Solovay Functions