Lebesgue density and classes

Journal of Symbolic Logic 81 (1):80-95 (2016)
  Copy   BIBTEX

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: thepositive density pointswith respect toeffectively closed sets of reals, and a proper subclass, thedensity-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.

Other Versions

No versions found

Links

PhilArchive

    This entry is not archived by us. If you are the author and have permission from the publisher, we recommend that you archive it. Many publishers automatically grant permission to authors to archive pre-prints. By uploading a copy of your work, you will enable us to better index it, making it easier to find.

    Upload a copy of this work     Papers currently archived: 102,546

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Denjoy, Demuth and density.Laurent Bienvenu, Rupert Hölzl, Joseph S. Miller & André Nies - 2014 - Journal of Mathematical Logic 14 (1):1450004.
Russell's typicality as another randomness notion.Athanassios Tzouvaras - 2020 - Mathematical Logic Quarterly 66 (3):355-365.
Schnorr Randomness.Rodney G. Downey & Evan J. Griffiths - 2004 - Journal of Symbolic Logic 69 (2):533 - 554.
Shift-complex sequences.Mushfeq Khan - 2013 - Bulletin of Symbolic Logic 19 (2):199-215.
Density of the Medvedev lattice of Π0 1 classes.Douglas Cenzer & Peter G. Hinman - 2003 - Archive for Mathematical Logic 42 (6):583-600.
Computational randomness and lowness.Sebastiaan Terwijn & Domenico Zambella - 2001 - Journal of Symbolic Logic 66 (3):1199-1205.

Analytics

Added to PP
2016-06-30

Downloads
18 (#1,140,088)

6 months
9 (#430,974)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations