License: 
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2012.543
URN: urn:nbn:de:0030-drops-34095
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2012/3409/
Bienvenu, Laurent ;
Hölzl, Rupert ;
Miller, Joseph S. ;
Nies, André
The Denjoy alternative for computable functions
Abstract
The Denjoy-Young-Saks Theorem from classical analysis states that for an arbitrary function f:R->R, the Denjoy alternative holds outside a null set, i.e., for almost every real x, either the derivative of f exists at x, or the derivative fails to exist in the worst possible way: the limit superior of the slopes around x equals +infinity, and the limit inferior -infinity. Algorithmic randomness allows us to define randomness notions giving rise to different concepts of almost everywhere. It is then natural to wonder which of these concepts corresponds to the almost everywhere notion appearing in the Denjoy-Young-Saks theorem. To answer this question Demuth investigated effective versions of the theorem and proved that Demuth randomness is strong enough to ensure the Denjoy alternative for Markov computable functions. In this paper, we show that the set of these points is indeed strictly bigger than the set of Demuth random reals - showing that Demuth's sufficient condition was too strong - and moreover is incomparable with Martin-Löf randomness; meaning in particular that it does not correspond to any known set of random reals. To prove these two theorems, we study density-type theorems, such as the Lebesgue density theorem and obtain results of independent interest. We show for example that the classical notion of Lebesgue density can be characterized by the only very recently defined notion of difference randomness. This is to our knowledge the first analytical characterization of difference randomness. We also consider the concept of porous points, a special type of Lebesgue nondensity points that are well-behaved in the sense that the "density holes" around the point are continuous intervals whose length follows a certain systematic rule. An essential part of our proof will be to argue that porous points of effectively closed classes can never be difference random.
BibTeX - Entry
@InProceedings{bienvenu_et_al:LIPIcs:2012:3409,
author = {Laurent Bienvenu and Rupert H{\"o}lzl and Joseph S. Miller and Andr{\'e} Nies},
title = {{The Denjoy alternative for computable functions}},
booktitle = {29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
pages = {543--554},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-35-4},
ISSN = {1868-8969},
year = {2012},
volume = {14},
editor = {Christoph D{\"u}rr and Thomas Wilke},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2012/3409},
URN = {urn:nbn:de:0030-drops-34095},
doi = {10.4230/LIPIcs.STACS.2012.543},
annote = {Keywords: Differentiability, Denjoy alternative, density, porosity, randomness}
}
|
Keywords: |
|
Differentiability, Denjoy alternative, density, porosity, randomness |
|
Collection: |
|
29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012) |
|
Issue Date: |
|
2012 |
|
Date of publication: |
|
24.02.2012 |
