A safe approximation for Kolmogorov complexity

DOI10.1007/978-3-319-11662-4_24MaRDI QIDQ2938743zbMATH OpenOpenAlexWikidataFDO

Authors Peter Bloem, Francisco Mota, Steven de Rooij, Luís Antunes, Pieter Adriaans

Publication date 14 January 2015

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://pure.uva.nl/ws/files/2408097/155469_SafeApproximation.CR.pdf

Mathematics Subject Classification ID

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

Recommendations

• On approximate uncomputability of the Kolmogorov complexity function
• Nonapproximability of the normalized information distance
• Kolmogorov Complexity with Error
• A computable measure of algorithmic probability by finite approximations with an application to integer sequences
• Methods and applications of algorithmic complexity. Beyond statistical lossless compression

Cited in

(6)

• A computable measure of algorithmic probability by finite approximations with an application to integer sequences
• On approximate uncomputability of the Kolmogorov complexity function
• Two Problems for Sophistication
• List approximation for increasing Kolmogorov complexity
• Cutting corners
• Nonapproximability of the normalized information distance

This page was built for publication: A safe approximation for Kolmogorov complexity

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