Oscillation in the initial segment complexity of random reals
type: Item
instance of: scholarly article
title: Oscillation in the initial segment complexity of random reals
zbMATH Open document ID: 1222.03047
author: Joseph S. Miller
author: Liang Yu
published in: Advances in Mathematics
publication date: 2011-03-29T00:00:00Z
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 \(< \…
Mathematics Subject Classification ID: 03D32
Mathematics Subject Classification ID: 68Q30
Mathematics Subject Classification ID: 03E35
zbMATH DE Number: 5871172
zbMATH Keywords: Kolmogorov complexity
zbMATH Keywords: \(K\)-degrees
zbMATH Keywords: initial segment complexity
zbMATH Keywords: effective randomness
reviewed by: Rodney G. Downey
MaRDI profile type: Publication
full work available at URL: j.aim.2010.12.022
OpenAlex ID: W2070615365
cites work: Randomness, lowness and degrees
cites work: Additivity of Measure Implies Additivity of Category
cites work: Q4844091
cites work: A Theory of Program Size Formally Identical to Information Theory
cites work: Incompleteness theorems for random reals
cites work: Q4779154
cites work: Randomness and reducibility
cites work: Algorithmic Randomness and Complexity
cites work: Q4136276
cites work: Every sequence is reducible to a random one
cites work: Borel Orderings
cites work: Set Theory
cites work: ∏ 0 1 Classes and Degrees of Theories
cites work: Lowness notions, measure and domination
cites work: Q3758821
cites work: Set theory. An introduction to independence proofs
cites work: An introduction to Kolmogorov complexity and its applications
cites work: The definition of random sequences
cites work: Complexity oscillations in infinite binary sequences
cites work: The \(K\)-degrees, low for \(K\) degrees, and weakly low for \(K\) sets
cites work: On initial segment complexity and degrees of randomness
cites work: Lowness properties and randomness
cites work: Q3611832
cites work: Q5606305
cites work: Q5559240
cites work: The axiomatization of randomness
cites work: The Kolmogorov complexity of random reals
cites work: THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
DOI: 10.1016/J.AIM.2010.12.022
description: scientific article; zbMATH DE number 5871172