Two Characterizations of Finite-State Dimension
Abstract
In this paper we provide two equivalent characterizations of the notion of finite-state dimension introduced by Dai, Lathrop, Lutz and Mayordomo (2004). One of them uses Shannon's entropy of non-aligned blocks and generalizes old results of Pillai (1940) and Niven-Zuckerman (1951). The second characterizes finite-state dimension in terms of superadditive functions that satisfy some calibration condition (in particular, superadditive upper bounds for Kolmogorov complexity). The use of superadditive bounds allows us to prove a general sufficient condition for normality that easily implies old results of Champernowne (1933), Besicovitch (1935), Copeland and Erdös (1946), and also a recent result of Calude, Staiger and Stephan (2016).
Origin | Files produced by the author(s) |
---|
Loading...