Denjoy, Demuth and density

, , &
Journal of Mathematical Logic 14 (1):1450004 (2014)
  Copy   BIBTEX

Abstract

We consider effective versions of two classical theorems, the Lebesgue density theorem and the Denjoy–Young–Saks theorem. For the first, we show that a Martin-Löf random real z ∈ [0, 1] is Turing incomplete if and only if every effectively closed class

Categories

Keywords

Reprint years

DOI

10.1142/s0219061314500044

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: 106,169

External links

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

Through your library

My notes

Similar books and articles

Lebesgue density and classes.Mushfeq Khan - 2016 - Journal of Symbolic Logic 81 (1):80-95.
Using almost-everywhere theorems from analysis to study randomness.Kenshi Miyabe, André Nies & Jing Zhang - 2016 - Bulletin of Symbolic Logic 22 (3):305-331.
Demuth randomness and computational complexity.Antonín Kučera & André Nies - 2011 - Annals of Pure and Applied Logic 162 (7):504-513.
Reviewed Work(s): Lowness properties and randomness. Advances in Mathematics, vol. 197 by André Nies; Lowness for the class of Schnorr random reals. SIAM Journal on Computing, vol. 35 by Bjørn Kjos-Hanssen; André Nies; Frank Stephan; Lowness for Kurtz randomness. The Journal of Symbolic Logic, vol. 74 by Noam Greenberg; Joseph S. Miller; Randomness and lowness notions via open covers. Annals of Pure and Applied Logic, vol. 163 by Laurent Bienvenu; Joseph S. Miller; Relativizations of randomness and genericity notions. The Bulletin of the London Mathematical Society, vol. 43 by Johanna N. Y. Franklin; Frank Stephan; Liang Yu; Randomness notions and partial relativization. Israel Journal of Mathematics, vol. 191 by George Barmpalias; Joseph S. Miller; André Nies. [REVIEW]Johanna N. Y. Franklin - forthcoming - Association for Symbolic Logic: The Bulletin of Symbolic Logic.
André Nies. Lowness properties and randomness. Advances in Mathematics, vol. 197 , no. 1, pp. 274–305. - Bjørn Kjos-Hanssen, André Nies, and Frank Stephan. Lowness for the class of Schnorr random reals. SIAM Journal on Computing, vol. 35 , no. 3, pp. 647–657. - Noam Greenberg and Joseph S. Miller. Lowness for Kurtz randomness. The Journal of Symbolic Logic, vol. 74 , no. 2, pp. 665–678. - Laurent Bienvenu and Joseph S. Miller. Randomness and lowness notions via open covers. Annals of Pure and Applied Logic, vol. 163 , no. 5, pp. 506–518. - Johanna N. Y. Franklin, Frank Stephan, and Liang. Yu Relativizations of randomness and genericity notions. The Bulletin of the London Mathematical Society, vol. 43 , no. 4, pp. 721–733. - George Barmpalias, Joseph S. Miller, and André Nies. Randomness notions and partial relativization. Israel Journal of Mathematics, vol. 191 , no. 2, pp. 791–816. [REVIEW]Johanna N. Y. Franklin - 2013 - Bulletin of Symbolic Logic 19 (1):115-118.
Randomness via infinite computation and effective descriptive set theory.Merlin Carl & Philipp Schlicht - 2018 - Journal of Symbolic Logic 83 (2):766-789.
Van Lambalgen's Theorem and High Degrees.Johanna N. Y. Franklin & Frank Stephan - 2011 - Notre Dame Journal of Formal Logic 52 (2):173-185.
The Sacks density theorem and Σ2-bounding.Marcia Groszek, Michael Mytilinaios & Theodore Slaman - 1996 - Journal of Symbolic Logic 61 (2):450 - 467.
The Sacks Density Theorem and $\Sigma_2$-Bounding.Marcia Groszek, Michael Mytilinaios & Theodore Slaman - 1996 - Journal of Symbolic Logic 61 (2):450-467.
Effective Fine‐convergence of Walsh‐Fourier series.Takakazu Mori, Mariko Yasugi & Yoshiki Tsujii - 2008 - Mathematical Logic Quarterly 54 (5):519-534.

Analytics

Added to PP
2014-03-25

Downloads
30 (#835,607)

6 months
4 (#1,001,261)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

The Equivalence of Definitions of Algorithmic Randomness.Christopher Porter - 2021 - Philosophia Mathematica 29 (2):153–194.
Computing from projections of random points.Noam Greenberg, Joseph S. Miller & André Nies - 2019 - Journal of Mathematical Logic 20 (1):1950014.
Lebesgue density and classes.Mushfeq Khan - 2016 - Journal of Symbolic Logic 81 (1):80-95.

Add more citations

References found in this work

Almost everywhere domination and superhighness.Stephen G. Simpson - 2007 - Mathematical Logic Quarterly 53 (4):462-482.
Randomness and computability: Open questions.Joseph S. Miller & André Nies - 2006 - Bulletin of Symbolic Logic 12 (3):390-410.
Demuth randomness and computational complexity.Antonín Kučera & André Nies - 2011 - Annals of Pure and Applied Logic 162 (7):504-513.
Almost everywhere domination.Natasha L. Dobrinen & Stephen G. Simpson - 2004 - Journal of Symbolic Logic 69 (3):914-922.
Demuth’s path to randomness.Antonín Kučera, André Nies & Christopher P. Porter - 2015 - Bulletin of Symbolic Logic 21 (3):270-305.

View all 7 references / Add more references