Oscillation in the initial segment complexity of random reals (Q633597)

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.