Effective Complexity

Effective complexity measures the information content of the regularities of an object. It has been introduced by Gell-Mann and Lloyd to avoid some of the disadvantages of Kolmogorov complexity. In these two talks, we report on recent work with Nihat Ay on effective complexity. In the first talk, we give a precise formal definition, and show that incompressible binary strings are effectively simple. Furthermore, we prove the existence of effectively complex strings, and relate effective complexity to Bennett's logical depth and to Kolmogorov minimal sufficient statistic. In the second talk, we apply effective complexity to ergodic processes. In particular, we show that typical realizations of computable ergodic processes are effectively simple.