The Kolmogorov complexity of real numbers. (Q1607299): Difference between revisions

We consider for a real number \(\alpha\) 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\cdot\log_{r}b\) prefix of the base \(r\) expansion of \(\alpha\) is the same (up to an additive constant) as the \(\log_{r}b\)-fold complexity of the length \(l\) prefix of the base \(b\) expansion of \(\alpha\). 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.