Problem #7
Kolmogorov-Loveland randomness vs Martin-Löf randomness
Does Kolmogorov-Loveland randomness imply Martin-Löf randomness?
Reference for the problem statement
Joseph S. Miller and André Nies, Randomness and computability: open questions, Bulletin of Symbolic Logic, 2006 [link] [doi]
Definitions
A sequence is Kolmogorov-Loveland random (KL-random for short) if no computable non-monotonic betting strategy can win infinitely much money playing against it. A sequence is Martin-Löf random (ML-random for short) if no c.e. monotonic betting strategy can win infinitely much money playing against it.
Known Partial Results
- Muchnik, Semenov and Uspensky proved that Martin-Löf randomness implies Kolmogorov-Loveland randomness.
- Merkle, Miller, Nies, Reimann and Stephan proved that if is KL-random then has arbitrarily dense subsequences which are ML-random.
Notes
This is often considered one of the most significant open problems in algorithmic randomness and has been open for close to 30 years.
Loading comments…