Approximating Kolmogorov complexity

DOI10.3233/com-200302MaRDI QIDQ6062178

Ruslan Ishkuvatov, Daniil Musatov, Alexander Shen

Publication date: 30 November 2023

Published in: Computability (Search for Journal in Brave)

zbMATH Keywords

approximationKolmogorov complexitymass problemscoarse computabilitygeneric computability

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Algorithmic randomness and dimension (03D32)

Cites Work

• On approximate uncomputability of the Kolmogorov complexity function
• The axiomatic power of Kolmogorov complexity
• Generic computability, Turing degrees, and asymptotic density
• The Surprise Examination Paradox and the Second Incompleteness Theorem
• Mass Problems and Randomness
• Kolmogorov Complexity and Algorithmic Randomness
• An introduction to Kolmogorov complexity and its applications
• Kolmogorov entropy in the context of computability theory
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Approximating Kolmogorov complexity