Prefix and plain Kolmogorov complexity characterizations of 2-randomness: simple proofs

DOI10.1007/s00153-015-0430-2zbMath1362.03037arXiv1310.5230OpenAlexW1993613819WikidataQ113906150 ScholiaQ113906150MaRDI QIDQ494650

Bruno Bauwens

Publication date: 1 September 2015

Published in: Archive for Mathematical Logic (Search for Journal in Brave)

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

zbMATH Keywords

incompressibilityMartin-Löf randomnessalgorithmic randomness2-randomnessrandomness deficiencyplain compexityprefix-free complexity

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Algorithmic randomness and dimension (03D32)

Related Items

Relating and contrasting plain and prefix Kolmogorov complexity ⋮ RANDOMNESS NOTIONS AND REVERSE MATHEMATICS ⋮ Coherence of reducibilities with randomness notions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Effectively approximating measurable sets by open sets
• The \(K\)-degrees, low for \(K\) degrees, and weakly low for \(K\) sets
• An additivity theorem for plain Kolmogorov complexity
• Limit complexities revisited
• Process complexity and effective random tests
• Algorithmic tests and randomness with respect to a class of measures
• Algorithmic Randomness and Complexity
• Exact Expressions for Some Randomness Tests
• A Theory of Program Size Formally Identical to Information Theory
• Every 2-random real is Kolmogorov random
• The definition of random sequences
• A formal theory of inductive inference. Part I
• Randomness, relativization and Turing degrees
• An introduction to Kolmogorov complexity and its applications