Constructive dimension equals Kolmogorov complexity
type: Item
instance of: scholarly article
title: Constructive dimension equals Kolmogorov complexity
zbMATH Open document ID: 1173.68542
author: Ludwig Staiger
published in: Information Processing Letters
publication date: 2009-08-27T00:00:00Z
Mathematics Subject Classification ID: 68Q30
Mathematics Subject Classification ID: 68Q05
zbMATH DE Number: 5599199
zbMATH Keywords: constructive dimension
zbMATH Keywords: Kolmogorov complexity
zbMATH Keywords: Levin's universal semi-measure
zbMATH Keywords: theory of computation
MaRDI profile type: Publication
full work available at URL: j.ipl.2004.09.023
OpenAlex ID: W2046221643
cites work: STACS 2004
cites work: On Hausdorff and topological dimensions of the Kolmogorov complexity of the real line
cites work: Q4375489
cites work: Gales suffice for constructive dimension
cites work: Q4337021
cites work: Dimension in Complexity Classes
cites work: Q2754206
cites work: The dimensions of individual strings and sequences
cites work: A Kolmogorov complexity characterization of constructive Hausdorff dimension.
cites work: Q5620774
cites work: Q3705346
cites work: Noiseless coding of combinatorial sources, Hausdorff dimension, and Kolmogorov complexity
cites work: The complexity and effectiveness of prediction algorithms
cites work: Kolmogorov complexity and Hausdorff dimension
cites work: A tight upper bound on Kolmogorov complexity and uniformly optimal prediction
cites work: The Kolmogorov complexity of real numbers.
cites work: A generalization of Chaitin's halting probability \(\Omega\) and halting self-similar sets
cites work: Relations between varieties of kolmogorov complexities
cites work: THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
DOI: 10.1016/J.IPL.2004.09.023
description: scientific article; zbMATH DE number 5599199