Limit complexities revisited

DOI10.4230/LIPICS.STACS.2008.1335MaRDI QIDQ4910709zbMATH OpenFDO

Authors Laurent Bienvenu, Andrej Muchnik, A. Shen, Nikolai K. Vereshchagin

Publication date 19 March 2013

Full work available at URL http://subs.emis.de/LIPIcs/frontdoor_5aa0.html

zbMATH Keywords

2-randomnessKolmogorov complexitylimit complexitieslimit frequencieslow basis

Mathematics Subject Classification ID

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

Recommendations

• Limit complexities revisited
• Prefix and plain Kolmogorov complexity characterizations of 2-randomness: simple proofs
• Every 2-random real is Kolmogorov random
• Relating and contrasting plain and prefix Kolmogorov complexity
• The Kolmogorov complexity of random reals

Cited in

(4)

• Limit complexities revisited
• A simple proof of Miller-Yu theorem
• LIMITING DYNAMICS FOR THE COMPLEX STANDARD FAMILY
• Prefix and plain Kolmogorov complexity characterizations of 2-randomness: simple proofs

This page was built for publication: Limit complexities revisited

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