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

\(K\)-degreeseffective randomnessinitial segment complexityKolmogorov complexity

Mathematics Subject Classification ID

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

Review text

Schnorr long ago showed that a real \(A\) is Martin-Löf random iff \(K(A\upharpoonright n)\geq n\) for all \(n\) (up to a constant) where \(A\upharpoonright n \) denotes the first \(n\) bits of \(A\) and \(K\) denotes prefix-free Kolmogorov complexity. Natural questions arise: How far can \(K(A\upharpoonright n)\) be above \(n\), how often is it close to \(n\), is there any gap behaviour or the like. This paper is devoted to questions like these. It follows in the tradition of early work by, particularly, Solovay and earlier Chaitin. The authors extend a result of Chaitin by giving a provably tight upper bound on the number of strings \(\sigma\) of length \(n\) with \(K(\sigma)<n+K(n)-m\). Using this proof, they show that \(\sum 2^{-g(n)}\) diverges iff \(\exists^\infty n\, K(A\upharpoonright n)>n+g(n)\) for all Martin-Löf random \(A\). This improves an earlier result of Solovay who had the result for \(g\) computable. Naturally, the general case is significantly more complex, and uses very different techniques. Miller and Yu use this result to prove that there are comparable \(K\)-degrees of random reals. Namely, there are 1-random \(A\) and \(B\) such that, for all \(n\), \(K(A\upharpoonright n)<^+ K(B\upharpoonright n)\), and these can be \(\Delta^0_2\). Also proven are facts about the size of downward and upward cones in the \(K\)-degrees. The techniques are ingenious and rely on machine simulations. Miller and Yu use a result of Erdős and Révész to give necessary and sufficient conditions on a function \(f\) so that \(K(A\upharpoonright n) \geq n+K(n) +f(n)\) for all \(n\) and for almost all \(A\), namely \(\sum 2^{-f(n)-K(f(n)|n^*)}<\infty\). If \(\sum 2^{-f(n)-K(f(n)|n^*)}=\infty\) then \(K(A\upharpoonright n) < n+K(n) +f(n)\) for all \(n\) and for almost all \(A\). A number of interesting corollaries are derived. Finally, in a completely different direction, it is shown that it is independent of ZFC whether every chain of 1-random \(K\)-degrees of size \(< \aleph_0^2\) has a lower bound in the 1-random \(K\)-degrees.

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

• 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
• 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?)
• 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 \(K\)-degrees, low for \(K\) degrees, and weakly low for \(K\) sets
• The axiomatization of randomness
• 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
• The Kolmogorov complexity of random reals
• ∏ 0 1 Classes and Degrees of Theories

Cited in

(10)

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

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)