skip to content

(Almost) Lowness for K and finite self-information

Tuesday 3rd July 2012 - 15:00 to 15:30
INI Seminar Room 1
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^{
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.
Presentation Material: 
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons