Randomness and Differentiability

Abstract. We characterize some major algorithmic randomness no-tions via differentiability of effective functions. (1) We show that a real number z ∈ [0, 1] is computably random if and only if every nondecreasing computable function [0, 1] → R is differen-tiable at z. (2) A real number z ∈ [0, 1] is weakly 2-random if and only if every almost everywhere differentiable computable function [0, 1] → R is dif-ferentiable at z. (3) Recasting results of the constructivist Demuth (1975) in classical language, we show that a real z is Martin-Löf random if and only if every computable function of bounded variation is differentiable at z, and similarly for absolutely continuous functions. We also use the analytic methods to show that computable random-ness of a real is base invariant, and to derive preservation results fo