Every 2-random real is Kolmogorov random
From MaRDI portal
Publication:5311760
DOI10.2178/jsl/1096901774zbMath1090.03012OpenAlexW1968044640MaRDI QIDQ5311760
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
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