Kolmogorov-Loveland randomness and stochasticity (Q2576945)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Kolmogorov-Loveland randomness and stochasticity
scientific article

    Statements

    Kolmogorov-Loveland randomness and stochasticity (English)
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    29 December 2005
    0 references
    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)\).
    0 references
    0 references
    0 references
    0 references
    0 references
    Kolmogorov-Loveland random sequences
    0 references
    Martin-Löf randomness
    0 references
    stochastic sequences
    0 references
    degrees of unsolvability
    0 references
    hyperimmune-free degrees
    0 references
    algorithmic randomness
    0 references
    effective Hausdorff dimension
    0 references
    effective randomness
    0 references
    Kolmogorov complexity
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references