The Kolmogorov complexity of random reals

DOI10.1016/j.apal.2004.01.006zbMath1065.03025MaRDI 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 complexity; random reals

Mathematics Subject Classification ID

68Q30: Algorithmic information theory (Kolmogorov complexity, etc.)

03D80: Applications of computability and recursion theory

Related Items

There are 2^{ℵ₀} many 𝐻-degrees in the random reals, Universal computably enumerable sets and initial segment prefix-free complexity, Effectively approximating measurable sets by open sets, Oscillation in the initial segment complexity of random reals, Kolmogorov complexity of initial segments of sequences and arithmetical definability, Information measures for infinite sequences, ON REALS WITH -BOUNDED COMPLEXITY AND COMPRESSIVE POWER, A minimal pair of 𝐾-degrees, Calibrating Randomness, On initial segment complexity and degrees of randomness

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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