A Safe Approximation for Kolmogorov Complexity

Thumbnail Image
Date
2014
Authors
Bloem,P
Mota,F
de Rooij,S
Luís Filipe Antunes
Adriaans,P
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Kolmogorov complexity (K) 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 (kappa) over bar to approximate K in a probabilistic sense: the probability that the error is greater than kappa decays exponentially with kappa. We apply the same method to the normalized information distance (NID) and discuss conditions that affect the safety of the approximation.
Description
Keywords
Citation