The Kolmogorov Complexity of Liouville Numbers

Reference

CDMTCS Research Reports CDMTCS-096 (1999)

Degree Grantor

Abstract

We consider for a real number a 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 which depends only on the relative information of one base with respect to the other. More precisely, we show that the complexity of the length . logr b prefix of the base r expansion of α is the same (up to an additive constant) as the logr b-fold complexity of the length l prefix of the base b expansion of α. Then we use this fact to derive complexity theoretic proofs for the base independence of the randomness of real numbers and for some properties of Liouville numbers.

Description

DOI

Related Link

Keywords

ANZSRC 2020 Field of Research Codes