Oscillation in the initial segment complexity of random reals

DOI10.1016/j.aim.2010.12.022zbMath1222.03047OpenAlexW2070615365MaRDI QIDQ633597

Liang Yu, Joseph S. Miller

Publication date: 29 March 2011

Published in: Advances in Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.aim.2010.12.022

zbMATH Keywords

Kolmogorov complexityinitial segment complexity\(K\)-degreeseffective randomness

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Consistency and independence results (03E35) Algorithmic randomness and dimension (03D32)

Related Items

Universal computably enumerable sets and initial segment prefix-free complexity ⋮ On initial segment complexity and degrees of randomness ⋮ Solovay functions and their applications in algorithmic randomness ⋮ Kolmogorov complexity of initial segments of sequences and arithmetical definability ⋮ Randomness and initial segment complexity for measures

Cites Work

• The \(K\)-degrees, low for \(K\) degrees, and weakly low for \(K\) sets
• Incompleteness theorems for random reals
• Set theory. An introduction to independence proofs
• Randomness and reducibility
• The Kolmogorov complexity of random reals
• Lowness properties and randomness
• Lowness notions, measure and domination
• Algorithmic Randomness and Complexity
• Additivity of Measure Implies Additivity of Category
• Borel Orderings
• Randomness, lowness and degrees
• On initial segment complexity and degrees of randomness
• Every sequence is reducible to a random one
• A Theory of Program Size Formally Identical to Information Theory
• Set Theory
• The axiomatization of randomness
• Complexity oscillations in infinite binary sequences
• 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
• ∏ 0 1 Classes and Degrees of Theories
• An introduction to Kolmogorov complexity and its applications
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Oscillation in the initial segment complexity of random reals