The Kolmogorov complexity of real numbers.
type: Item
instance of: scholarly article
title: The Kolmogorov complexity of real numbers.
zbMATH Open document ID: 1042.68056
DOI: 10.1016/S0304-3975(01)00102-5
author: Ludwig Staiger
published in: Theoretical Computer Science
publication date: 2002-07-31T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q30
zbMATH DE Number: 1774172
zbMATH Keywords: Kolmogorov complexity
zbMATH Keywords: base expansion
zbMATH Keywords: omega-words
zbMATH Keywords: Liouville numbers
zbMATH Keywords: disjunctive omega-words
MaRDI profile type: Publication
cites work: On Hausdorff and topological dimensions of the Kolmogorov complexity of the real line
cites work: Q4326782
cites work: Are binary codings universal?
cites work: Results and trends in theoretical computer science, Colloquium in honor of Arto Salomaa, Graz, Austria, June 10-11, 1994. Proceedings
cites work: On a problem of Steinhaus about normal numbers
cites work: Information, randomness and incompleteness. Papers on algorithmic information theory
cites work: The extent and density of sequences within the minimal-program complexity hierarchies
cites work: Q3714302
cites work: Q4942048
cites work: Q4219053
cites work: Q4023358
cites work: Fractals, dimension, and formal languages
cites work: Q5620774
cites work: Noiseless coding of combinatorial sources, Hausdorff dimension, and Kolmogorov complexity
cites work: On normal numbers
cites work: Kolmogorov complexity and Hausdorff dimension
cites work: A tight upper bound on Kolmogorov complexity and uniformly optimal prediction
cites work: THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
description: scientific article; zbMATH DE number 1774172