The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

Skip to content



(Almost) Lowness for K and finite self-information

Herbert, I (University of California, Berkeley)
Tuesday 03 July 2012, 15:00-15:30

Seminar Room 1, Newton Institute


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.


[pdf ]


The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.

Back to top ∧