科研之友
微信
新浪微博
Facebook
分享链接
摘要
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 " of random real z is an element of [0, 1] is Turing incomplete if and only if every effectively closed class C subset of [0, 1] containing z has positive density at z. Under the stronger assumption that z is not LR-hard, we show that every such class has density one at z. These results have since been applied to solve two open problems on the interaction between the Turing degrees of Martin-Lof random reals and K-trivial sets: the noncupping and covering problems. We say that f : [0, 1] -> R satisfies the Denjoy alternative at z is an element of [0, 1] if either the derivative f'(z) exists, or the upper and lower derivatives at z are +infinity and -infinity, respectively. The Denjoy-Young-Saks theorem states that every function f : [0, 1]-> R satisfies the Denjoy alternative at almost every z is an element of [0, 1]. We answer a question posed by Kucera in 2004 by showing that a real z is computably random if and only if every computable function f satisfies the Denjoy alternative at z. For Markov computable functions, which are only defined on computable reals, we can formulate the Denjoy alternative using pseudoderivatives. Call a real z DA-random if every Markov computable function satisfies the Denjoy alternative at z. We considerably strengthen a result of Demuth (Comment. Math. Univ. Carolin. 24(3) (1983) 391-406) by showing that every Turing incomplete Martin-Lof random real is DA-random. The proof involves the notion of nonporosity, a variant of density, which is the bridge between the two themes of this paper. We finish by showing that DA-randomness is incomparable with Martin-Lof randomness.
- 出版日期2014-6
