Compressibility and Kolmogorov complexity
type: Item
instance of: scholarly article
title: Compressibility and Kolmogorov complexity
zbMATH Open document ID: 1271.03058
DOI: 10.1215/00294527-1731416
author: Stephen Binns
author: Marie Nicholson
published in: Notre Dame Journal of Formal Logic
publication date: 2013-01-30T00:00:00Z
full work available at URL: https://projecteuclid.org/euclid.ndjfl/1355494526
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.
reviewed by: Liang Yu
Mathematics Subject Classification ID: 03D32
Mathematics Subject Classification ID: 68Q30
zbMATH DE Number: 6132728
zbMATH Keywords: effective Hausdorff dimension
zbMATH Keywords: effective packing dimension
zbMATH Keywords: Kolmogorov complexity
zbMATH Keywords: computability
zbMATH Keywords: effective metric
MaRDI profile type: Publication
OpenAlex ID: W2020872041
cites work: Effective Strong Dimension in Algorithmic Information and Computational Complexity
cites work: Relative Kolmogorov complexity and geometry
cites work: Turing degrees of reals of positive effective packing dimension
cites work: Algorithmic Randomness and Complexity
cites work: Randomness and reducibility
cites work: Dimension in Complexity Classes
cites work: A Kolmogorov complexity characterization of constructive Hausdorff dimension.
cites work: Q3611832
cites work: Q5697037
cites work: Two definitions of fractional dimension
description: scientific article; zbMATH DE number 6132728