The Denjoy alternative for computable functions

29th International Symposium on Theoretical Aspects of Computer Science

Laurent Bienvenu1, Rupert Hölzl∗2, Joseph S. Miller†3, and André Nies4 ; 3 Department of Mathematics ; University of Wisconsin ; Madison ; WI 53706-1388 ; USA ; 4 Department of Computer Science ; University of Auckland ; Private Bag 92019 ; Auckland ; New Zealand

Others  :  http://drops.dagstuhl.de/opus/volltexte/2012/3409/pdf/25.pdf
PID  :  44539

来源: CEUR

【 摘 要 】

The Denjoy-Young-Saks Theorem from classical analysis states that for an arbitrary function f : ℝ → ℝ, 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 +∞, and the limit inferior −∞. 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 results, 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 the first analytical characterization of difference randomness. We also consider the concept of porous points, a special type of Lebesgue non-density points for which drops in density are witnessed by single intervals. An essential part of our proof will be to argue that porous points of effectively closed classes can never be difference random.1998 ACM Subject Classification F.1.1 Models of Computation