The Kolmogorov complexity of random reals

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

zbMATH Keywords

Kolmogorov complexityrandom reals

Mathematics Subject Classification ID

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

This page was built for publication: The Kolmogorov complexity of random reals