Feasible analysis, randomness, and base invariance

SANTIAGO FIGUEIRA; ANDRÉ NIES

THEORY OF COMPUTING SYSTEMS

SPRINGER

Lugar: Berlin; Año: 2015 vol. 56 p. 439 - 464

1432-4350

We show that polynomial time randomness of a real number does not depend on the choice of a base for representing it. Our main tool is an "almost Lipschitz" condition that we show for the cumulative distribution function associated to martingales with the savings property. Based on a result of Schnorr, we prove that for any base r, n*log2 n-randomness in base r implies normality in base r, and that n4-randomness in base r implies absolute normality. Our methods yield a construction of an absolutely normal real number which is computable in polynomial time.