SAS

Abstract

A real $X$, is called low for K if there is a constant $c$ such that using $X$ as an oracle does not decrease the Kolmogorov complexity of any string by more than $c$. That is, the inequality $K(\sigma) \leq K^{X}(\sigma) +c$ holds for all $\sigma \in 2^{<\omega}$. One can relax this definition by replacing the constant with a slow growing function $f$ and one obtains reals that are `almost' low for $K$ `up to $f$'. It is not surprising that there are reals that are `almost' low for $K$ but not actually low for $K$, but the classes of reals that are 'almost' low for $K$ and those that are low for $K$ in the traditional sense can behave very differently. We will explain some of these results, and in particular discuss how they relate to one definition of mutual information.