On approximate uncomputability of the Kolmogorov complexity function

DOI10.1007/978-3-030-22996-2_20zbMATH Open1434.68209OpenAlexW2955446419MaRDI QIDQ2179366FDOQ2179366

Authors: Ruslan Ishkuvatov, Daniil Musatov 

Publication date: 12 May 2020

Full work available at URL: https://doi.org/10.1007/978-3-030-22996-2_20

Recommendations

• A safe approximation for Kolmogorov complexity
• Kolmogorov Complexity with Error
• Randomized communication complexity of approximating Kolmogorov complexity
• Estimates of Kolmogorov complexity in approximating Cantor sets
• scientific article; zbMATH DE number 107774

Mathematics Subject Classification ID

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

Cited In (9)

• List approximation for increasing Kolmogorov complexity
• A safe approximation for Kolmogorov complexity
• Asymptotic density and the coarse computability bound
• Estimates of Kolmogorov complexity in approximating Cantor sets
• Kolmogorov Complexity with Error
• HIERARCHIES OF GENERALIZED KOLMOGOROV COMPLEXITIES AND NONENUMERABLE UNIVERSAL MEASURES COMPUTABLE IN THE LIMIT
• Randomized communication complexity of approximating Kolmogorov complexity
• Approximating Kolmogorov complexity
• Non-approximability of the Randomness Deficiency Function

This page was built for publication: On approximate uncomputability of the Kolmogorov complexity function

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