1 results
LEBESGUE DENSITY AND
$\prod _1^0$ CLASSES
-
- Journal:
- The Journal of Symbolic Logic / Volume 81 / Issue 1 / March 2016
- Published online by Cambridge University Press:
- 09 March 2016, pp. 80-95
- Print publication:
- March 2016
-
- Article
- Export citation
-
Analyzing the effective content of the Lebesgue density theorem played a crucial role in some recent developments in algorithmic randomness, namely, the solutions of the ML-covering and ML-cupping problems. Two new classes of reals emerged from this inquiry: the positive density points with respect to effectively closed (or
$\prod _1^0$) sets of reals, and a proper subclass, the density-one points. Bienvenu, Hölzl, Miller, and Nies have shown that the Martin-Löf random positive density points are exactly the ones that do not compute the halting problem. Treating this theorem as our starting point, we present several new results that shed light on how density, randomness, and computational strength interact.
