A Safe Approximation for Kolmogorov Complexity
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 ${\overline{\kappa}}$ to approximate K in a probabilistic sense: the probability that the error is greater than k decays exponentially with k . We apply the same method to the normalized information distance (NID) and discuss conditions that affect the safety of the approximation.
Cite
Text
Bloem et al. "A Safe Approximation for Kolmogorov Complexity." International Conference on Algorithmic Learning Theory, 2014. doi:10.1007/978-3-319-11662-4_24Markdown
[Bloem et al. "A Safe Approximation for Kolmogorov Complexity." International Conference on Algorithmic Learning Theory, 2014.](https://mlanthology.org/alt/2014/bloem2014alt-safe/) doi:10.1007/978-3-319-11662-4_24BibTeX
@inproceedings{bloem2014alt-safe,
title = {{A Safe Approximation for Kolmogorov Complexity}},
author = {Bloem, Peter and Mota, Francisco and de Rooij, Steven and Antunes, Luis and Adriaans, Pieter},
booktitle = {International Conference on Algorithmic Learning Theory},
year = {2014},
pages = {336-350},
doi = {10.1007/978-3-319-11662-4_24},
url = {https://mlanthology.org/alt/2014/bloem2014alt-safe/}
}