How incomputable is Kolmogorov complexity?

Abstract

Kolmogorov complexity is the length of the ultimately compressed version of a file (that is, anything which can be put in a computer). Formally, it is the length of a shortest program from which the file can be reconstructed. We discuss the incomputabilty of Kolmogorov complexity, which formal loopholes this leaves us, recent approaches to compute or approximate Kolmogorov complexity, which approaches are problematic and which approaches are viable.

9 pages LaTeX

Cited by in corpus (4)

• A Review of Methods for Estimating Algorithmic Complexity: Options, Challenges, and New Directions
• Complex systems approach to natural language
• A Note on A Priori Forecasting and Simplicity Bias in Time Series
• Investigating Estimated Kolmogorov Complexity as a Means of Regularization for Link Prediction