On the invariance of the Kolmogorov complexity of ß-expansions

Authors

Valentin Abadie and Helmut Bölcskei

Reference

arXiv:2405.03816, May 2024.

Abstract

Measuring the complexity of real numbers is of major importance in computer science, for the purpose of knowing which computations are allowed. Consider a non-computable real number s, i.e. a real number which cannot be stored on a computer. We can store only an approximation of x, for instance by considering a finite bitstring representing a finite prefix of its binary expansion. For a fixed approximation error ε>0, the size of this finite bitstring is dependent on the \textit{algorithmic complexity} of the finite prefixes of the binary expansion of s. The \textit{algorithmic complexity} of a binary sequence x, often referred to as \textit{Kolmogorov complexity}, is the length of the smallest binary sequence x′, for which there exists an algorithm, such that when presented with x′ as input, it outputs x. The algorithmic complexity of the binary expansion of real numbers is widely studied, but the algorithmic complexity of other ways of representing real numbers remains poorly reported. However, knowing the algorithmic complexity of different representations may allow to define new and more efficient strategies to represent real numbers. Several papers have established an equivalence between the algorithmic complexity of the q-ary expansions, with q∈ℕ, q≥2, i.e. representations of real numbers in any integer base. In this paper, we study the algorithmic complexity of the so-called β-expansions, which are representations of real numbers in a base β∈(1,2) that display a much more complex behavior as compared to the q-ary expansion. We show that for a given real number s, the binary expansion is a minimizer of algorithmic complexity, and that for every given β∈(1,2), there exists a β-expansion of s which achieves the lower bound of algorithmic complexity displayed by the binary expansion of s.

Download this document:

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.