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

Mathematics Subject Classification ID

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

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

Cited in

(9)

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

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)