Gales suffice for constructive dimension

DOI10.1016/S0020-0190(02)00454-4zbMath1162.68462MaRDI QIDQ1007560

John M. Hitchcock

Publication date: 23 March 2009

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

computational complexityconstructive dimensiongales

Mathematics Subject Classification ID

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

Related Items

Constructive dimension equals Kolmogorov complexity ⋮ The dimensions of individual strings and sequences ⋮ Random sequences with respect to a measure defined by two linear fractional transformations ⋮ Dimension, entropy rates, and compression ⋮ A characterization of constructive dimension ⋮ Scaled dimension and the Kolmogorov complexity of Turing-hard sets ⋮ Dimension extractors and optimal decompression

Cites Work

• Unnamed Item
• Unnamed Item
• Almost everywhere high nonuniform complexity
• Zufälligkeit und Wahrscheinlichkeit. Eine algorithmische Begründung der Wahrscheinlichkeitstheorie. (Randomness and probability. An algorithmic foundation of probability theory)
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
• A unified approach to the definition of random sequences
• The definition of random sequences

This page was built for publication: Gales suffice for constructive dimension