The sum \(2^{KM(x)-K(x)}\) over all prefixes \(x\) of some binary sequence can be infinite

DOI10.1007/s00224-014-9604-2zbMath1339.68126arXiv1401.1467OpenAlexW2002095405MaRDI QIDQ285515

Akim Kumok, Mikhail Andreev

Publication date: 19 May 2016

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1401.1467

zbMATH Keywords

Kolmogorov complexitya priori probabilityalgorithmic randomness

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Process complexity and effective random tests
• Algorithmic tests and randomness with respect to a class of measures
• On initial segment complexity and degrees of randomness
• Exact Expressions for Some Randomness Tests
• A Theory of Program Size Formally Identical to Information Theory
• Kolmogorov Complexity and Algorithmic Randomness
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
• The definition of random sequences

This page was built for publication: The sum \(2^{KM(x)-K(x)}\) over all prefixes \(x\) of some binary sequence can be infinite