Kolmogorov complexity conditional to large integers

DOI10.1016/S0304-3975(01)00031-7MaRDI QIDQ5958282zbMATH OpenFDO

Authors Nikolai K. Vereshchagin

Publication date 3 March 2002

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0304-3975(01)00031-7

zbMATH Keywords

busy beaver functionKolmogorov complexityrelativized Kolmogorov complexity

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 5294121
• Kolmogorov complexity
• Approximating Kolmogorov complexity
• scientific article; zbMATH DE number 2196513
• scientific article; zbMATH DE number 107775
• Kolmogorov complexity for possibly infinite computations
• Kolmogorov complexity and set theoretical representations of integers
• Kolmogorov complexity arguments in combinatorics
• Publication:4934359

Cites work

• scientific article; zbMATH DE number 412149 (Why is no real title available?)
• scientific article; zbMATH DE number 1304316 (Why is no real title available?)
• scientific article; zbMATH DE number 1010621 (Why is no real title available?)
• scientific article; zbMATH DE number 3214538 (Why is no real title available?)
• Lower Limits of Frequencies in Computable Sequences and Relativized a Priori Probability
• On Kolmogorov's complexity and information
• On the relation between descriptional complexity and algorithmic probability
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS

Cited in

(5)

• Limit complexities revisited
• Descriptive complexity of computable sequences revisited
• Complexity of complexity and maximal plain versus prefix-free Kolmogorov complexity
• Upper semi-lattice of binary strings with the relation ``\(x\) is simple conditional to \(y\)
• The Kolmogorov birthday paradox

This page was built for publication: Kolmogorov complexity conditional to large integers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5958282)