Two sources are better than one for increasing the Kolmogorov complexity of infinite sequences

DOI10.1007/s00224-009-9214-6zbMath1205.68182arXiv0705.4658OpenAlexW2094688861MaRDI QIDQ987377

Marius Zimand

Publication date: 13 August 2010

Published in: Theory of Computing Systems, Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0705.4658

zbMATH Keywords

Hausdorff dimensionKolmogorov complexity

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Related Items

Randomness, Computation and Mathematics ⋮ Extracting information is hard: a Turing degree of non-integral effective Hausdorff dimension ⋮ Algorithmically Independent Sequences ⋮ Short lists with short programs in short time ⋮ On Generating Independent Random Strings ⋮ Algorithmically independent sequences ⋮ Turing degrees of reals of positive effective packing dimension ⋮ Extracting Kolmogorov complexity with applications to dimension zero-one laws ⋮ Constructive dimension and Turing degrees ⋮ On extracting space-bounded Kolmogorov complexity

Cites Work

• Constructive dimension equals Kolmogorov complexity
• Dimension extractors and optimal decompression
• A Kolmogorov complexity characterization of constructive Hausdorff dimension.
• The dimensions of individual strings and sequences
• Randomness and Computability: Open Questions
• Algorithmically Independent Sequences
• Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws
• Extracting the Kolmogorov Complexity of Strings and Sequences from Sources with Limited Independence
• Constructive Dimension and Weak Truth-Table Degrees
• STACS 2005
• Extracting Randomness Using Few Independent Sources
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item