The Kolmogorov complexity of real numbers

AbstractWe consider for a real number α the Kolmogorov complexities of its expansions with respect to different bases. In the paper it is shown that, for usual and self-delimiting Kolmogorov complexity, the complexity of the prefixes of their expansions with respect to different bases r and b are related in a way that depends only on the relative information of one base with respect to the other.More precisely, we show that the complexity of the length l·logrb prefix of the base r expansion of α is the same (up to an additive constant) as the logrb-fold complexity of the length l prefix of the base b expansion of α.Then we consider the classes of reals of maximum and minimum complexity. For maximally complex reals we use our result to derive a further complexity theoretic proof for the base independence of the randomness of real numbers.Finally, we consider Liouville numbers as a natural class of low complex real numbers