Compressibility and Kolmogorov complexity

DOI10.1215/00294527-1731416MaRDI QIDQ1934957zbMATH OpenOpenAlexFDO

Authors Stephen Binns, Marie Nicholson

Publication date 30 January 2013

Published in Notre Dame Journal of Formal Logic (Search for Journal in Brave)

Full work available at URL https://projecteuclid.org/euclid.ndjfl/1355494526

zbMATH Keywords

computabilityeffective Hausdorff dimensioneffective metriceffective packing dimensionKolmogorov complexity

Mathematics Subject Classification ID

Algorithmic randomness and dimension (03D32) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Review text

In the paper under review, the authors investigated a metric space over \(2^{\omega}\) defined by \(d(x,y)=\overline{\lim}_n \frac{C(x\upharpoonright n|y\upharpoonright n)}{n}\). They prove that, among the others, for any \(\alpha\in [0,1]\), \(d(\alpha\cdot x, \alpha \cdot y)=\alpha\cdot d(x,y)\); and \(2^{\omega}\) is path connected.

Recommendations

• On Hausdorff and topological dimensions of the Kolmogorov complexity of the real line
• Relative Kolmogorov complexity and geometry
• Completeness, Compactness, Effective Dimensions
• scientific article; zbMATH DE number 17560
• Kolmogorov complexity and Hausdorff dimension

Cites work

• A Kolmogorov complexity characterization of constructive Hausdorff dimension.
• Algorithmic randomness and complexity.
• Computability and randomness
• Dimension in Complexity Classes
• Effective Strong Dimension in Algorithmic Information and Computational Complexity
• scientific article; zbMATH DE number 2216397 (Why is no real title available?)
• Randomness and reducibility
• Relative Kolmogorov complexity and geometry
• Turing degrees of reals of positive effective packing dimension
• Two definitions of fractional dimension

Cited in

(11)

• Compression and diffusion: a joint approach to detect complexity.
• Entropy compression versus Lovász local lemma
• Compressibility and resource bounded measure
• Compression and hadamard power inequalities
• scientific article; zbMATH DE number 1998343 (Why is no real title available?)
• Construction of expanders and superconcentrators using Kolmogorov complexity
• Compressibility of Deterministic and Random Infinite Sequences
• Compressibility and resource bounded measure
• Sequential codes, lossless compression of individual sequences, and Kolmogorov complexity
• Compression is Comprehension and the Unreasonable Effectiveness of Digital Computation in the Natural World
• Disk compression of k-mer sets

This page was built for publication: Compressibility and Kolmogorov complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1934957)