The Kolmogorov complexity of random reals
From MaRDI portal
Publication:1887661
DOI10.1016/j.apal.2004.01.006zbMath1065.03025OpenAlexW2135826414MaRDI QIDQ1887661
Liang Yu, Rodney G. Downey, Ding, Decheng
Publication date: 22 November 2004
Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.apal.2004.01.006
Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Applications of computability and recursion theory (03D80)
Related Items
There are 2^{ℵ₀} many 𝐻-degrees in the random reals ⋮ Universal computably enumerable sets and initial segment prefix-free complexity ⋮ On the complexity of algebraic numbers, and the bit-complexity of straight-line programs1 ⋮ On initial segment complexity and degrees of randomness ⋮ Effectively approximating measurable sets by open sets ⋮ Oscillation in the initial segment complexity of random reals ⋮ ON REALS WITH -BOUNDED COMPLEXITY AND COMPRESSIVE POWER ⋮ Information measures for infinite sequences ⋮ Kolmogorov complexity of initial segments of sequences and arithmetical definability ⋮ A minimal pair of 𝐾-degrees ⋮ Calibrating Randomness
Cites Work
- Incompleteness theorems for random reals
- Zufälligkeit und Wahrscheinlichkeit. Eine algorithmische Begründung der Wahrscheinlichkeitstheorie. (Randomness and probability. An algorithmic foundation of probability theory)
- Randomness and Recursive Enumerability
- Algorithmic Randomness and Complexity
- Von Mises' definition of random sequences reconsidered
- A Theory of Program Size Formally Identical to Information Theory
- There are 2^{ℵ₀} many 𝐻-degrees in the random reals
- THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
- The definition of random sequences
- A formal theory of inductive inference. Part II
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
