Effectively approximating measurable sets by open sets

DOI10.1016/j.tcs.2012.01.011zbMath1250.03070MaRDI QIDQ418744

Chris J. Conidis

Publication date: 30 May 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2012.01.011

zbMATH Keywords

Kolmogorov complexity; computability theory; measure theory; algorithmic randomness

Mathematics Subject Classification ID

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

03D45: Theory of numerations, effectively presented structures

28E15: Other connections with logic and set theory

03D32: Algorithmic randomness and dimension

Related Items

RANDOMNESS NOTIONS AND REVERSE MATHEMATICS, Prefix and plain Kolmogorov complexity characterizations of 2-randomness: simple proofs, Coherence of reducibilities with randomness notions, Computability on measurable functions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The \(K\)-degrees, low for \(K\) degrees, and weakly low for \(K\) sets
• The Kolmogorov complexity of random reals
• Limit complexities revisited
• Lowness notions, measure and domination
• Algorithmic Randomness and Complexity
• Uniform almost everywhere domination
• Calibrating Randomness
• Low for random reals and positive-measure domination
• Every 2-random real is Kolmogorov random
• Randomness, relativization and Turing degrees