Normality and Differentiability

VERÓNICA BECHER; PABLO ARIEL HEIBER

Cambridge

Congreso; Computability Complexity and Randomness; 2012

Isaac Newton Institute

We translate the classical theorem of numerical analysis "Every non-decreasing function is almost everywhere differentiable" to the world of functions computable by finite automata and obtain the following Theorem: A real number is normal to a given base if, and only if, every real valued non-decreasing function computable by a finite automata is differentiable at the expansion of the real number in that base. The proof relies in the characterization of normal sequences as those incompressible by lossless finite-state compressors. These are finite automata endowed with an output function such that the automata input/output behaviour is injective.