Oscillation in the initial segment complexity of random reals

DOI10.1016/J.AIM.2010.12.022MaRDI QIDQ633597zbMATH OpenOpenAlexFDO

Authors Joseph S. Miller, Liang Yu

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 randomness and dimension (03D32) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Consistency and independence results (03E35)

Recommendations

• The Kolmogorov complexity of random reals
• On initial segment complexity and degrees of randomness
• Randomness, relativization and Turing degrees
• The \(K\)-degrees, low for \(K\) degrees, and weakly low for \(K\) sets
• Initial segment complexities of randomness notions

Cites work

• scientific article; zbMATH DE number 4008384 (Why is no real title available?)
• scientific article; zbMATH DE number 3564005 (Why is no real title available?)
• scientific article; zbMATH DE number 1834658 (Why is no real title available?)
• scientific article; zbMATH DE number 787541 (Why is no real title available?)
• scientific article; zbMATH DE number 3275577 (Why is no real title available?)
• scientific article; zbMATH DE number 3327849 (Why is no real title available?)
• A Theory of Program Size Formally Identical to Information Theory
• Additivity of Measure Implies Additivity of Category
• Algorithmic randomness and complexity.
• An introduction to Kolmogorov complexity and its applications
• Borel Orderings
• Complexity oscillations in infinite binary sequences
• Computability and randomness
• Every sequence is reducible to a random one
• Incompleteness theorems for random reals
• Lowness notions, measure and domination
• Lowness properties and randomness
• On initial segment complexity and degrees of randomness
• Randomness and reducibility
• Randomness, lowness and degrees
• Set Theory
• Set theory. An introduction to independence proofs
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
• The Kolmogorov complexity of random reals
• The \(K\)-degrees, low for \(K\) degrees, and weakly low for \(K\) sets
• The axiomatization of randomness
• The definition of random sequences
• ∏ 0 1 Classes and Degrees of Theories

Cited in

(9)

• Solovay functions and their applications in algorithmic randomness
• Universal computably enumerable sets and initial segment prefix-free complexity
• Lower bounds on the redundancy in computations from random oracles via betting strategies with restricted wagers
• The \(K\)-degrees, low for \(K\) degrees, and weakly low for \(K\) sets
• Randomness, relativization and Turing degrees
• Randomness and initial segment complexity for measures
• Every 2-random real is Kolmogorov random
• Kolmogorov complexity of initial segments of sequences and arithmetical definability
• On initial segment complexity and degrees of randomness

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q633597)