Kolmogorov-Loveland randomness and stochasticity (Q2576945)

In the paper under review the authors prove that for every effective split of a Kolmo\-gorov-Love\-land random sequence at least one of the parts is Martin-Löf random. It follows that every Kolmo\-gorov-Love\-land random sequence has arbitrarily dense subsequences that are Martin-Löf random. This result gives a partial answer to a well-known open problem in the field of effective randomness, that is, whether Martin-Löf randomness is the same as Kolmogorov-Loveland randomness. However, the authors also construct a sequence that is not even computably random such that every effective split yields two subsequences that are 2-random. This means that the splitting property does not characterize Kolmogorov-Loveland randomness. Moreover, the authors prove that for any Kolmogorov-Loveland random sequence \(A\) which is Turing reducible to the halting problem, the following holds: for any effective split of \(A\) both its parts are Martin-Löf random, and for any computable nondecreasing and nonbounded function \(g\) and almost all integers \(n\), the prefix of \(A\) of length \(n\) has prefix-free Kolmogorov complexity at least \(n-g(n)\).