Kolmogorov Complexity and Solovay Functions

Laurent Bienvenu, Rod Downey

Solovay proved that there exists a computable upper bound f of the prefix-free Kolmogorov complexity function K such that f (x) = K(x) for infinitely many x. In this paper, we cons…