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 (13)
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
This page was built for publication: Every 2-random real is Kolmogorov random