Back to Search Start Over

LEBESGUE DENSITY AND $\prod _1^0$ CLASSES.

Authors :
KHAN, MUSHFEQ
Source :
Journal of Symbolic Logic; Mar2016, Vol. 81 Issue 1, p80-95, 16p
Publication Year :
2016

Abstract

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. [ABSTRACT FROM PUBLISHER]

Details

Language :
English
ISSN :
00224812
Volume :
81
Issue :
1
Database :
Supplemental Index
Journal :
Journal of Symbolic Logic
Publication Type :
Academic Journal
Accession number :
113600893
Full Text :
https://doi.org/10.1017/jsl.2015.66