Problem #7

Kolmogorov-Loveland randomness vs Martin-Löf randomness

Open!!High impact — resolution would likely be publishable in a top journal (Advances-level or above)

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 X2NX \in 2^\mathbb{N} 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 X2NX \in 2^\mathbb{N} 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 XX is KL-random then XX 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.

Comments

Loading comments…