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
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
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