Compressibility and Kolmogorov complexity

DOI10.1215/00294527-1731416zbMath1271.03058OpenAlexW2020872041MaRDI QIDQ1934957

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

Kolmogorov complexitycomputabilityeffective packing dimensioneffective Hausdorff dimensioneffective metric

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Turing degrees of reals of positive effective packing dimension
• A Kolmogorov complexity characterization of constructive Hausdorff dimension.
• Randomness and reducibility
• Relative Kolmogorov complexity and geometry
• Algorithmic Randomness and Complexity
• Effective Strong Dimension in Algorithmic Information and Computational Complexity
• Two definitions of fractional dimension
• Dimension in Complexity Classes

This page was built for publication: Compressibility and Kolmogorov complexity