Every 2-random real is Kolmogorov random

DOI10.2178/jsl/1096901774zbMath1090.03012OpenAlexW1968044640MaRDI QIDQ5311760

Joseph S. Miller

Publication date: 29 August 2005

Published in: Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2178/jsl/1096901774

zbMATH Keywords

Kolmogorov complexityMartin-Löf random sequenceKolmogorov randomnessKolmogorov random sequence

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Applications of computability and recursion theory (03D80)

Related Items

Relating and contrasting plain and prefix Kolmogorov complexity, What Percentage of Programs Halt?, Initial segment complexities of randomness notions, Depth, Highness and DNR Degrees, On the complexity of algebraic numbers, and the bit-complexity of straight-line programs1, RANDOMNESS NOTIONS AND REVERSE MATHEMATICS, On initial segment complexity and degrees of randomness, Effectively approximating measurable sets by open sets, Prefix and plain Kolmogorov complexity characterizations of 2-randomness: simple proofs, Coherence of reducibilities with randomness notions, BEING LOW ALONG A SEQUENCE AND ELSEWHERE, Randomness and Computability: Open Questions, Calibrating Randomness

Cites Work

• Unnamed Item
• Algorithmic Complexity and Randomness: Recent Developments
• A Theory of Program Size Formally Identical to Information Theory
• Complexity oscillations in infinite binary sequences
• A unified approach to the definition of random sequences
• The definition of random sequences
• A formal theory of inductive inference. Part II