A safe approximation of Kolmogorov complexity
Kolmogorov complexity is an incomputable function. It can be approximated from above but not to arbitrary given precision and it cannot be approximated from below. By restricting the source of the data to a specific model class, we can construct a computable function to approximate the Kolmogorov complexity in a probabilistic sense: the probability that the error is greater than k bits decays exponentially with k. We apply the same method to the normalized information distance and discuss conditions that affect the safety of the approximation.