Computability Learning Seminar

Cole Wyeth, University of Waterloo

Introduction to Algorithmic Complexity

The Kolmogorov complexity of an object is the size of the smallest "self-extracting archive" that could have generated it, which can be viewed as an algorithmic information content. For instance, an image of the Mandelbrot set (to finite resolution) may appear quite visually complex, but is actually rather algorithmically simple since it requires only a short rule and iteration number to generate it, while typical noise is algorithmically complex. In this introductory talk, I will introduce the plain and prefix versions of the Kolmogorov complexity along with some of their basic properties such as (in)computability level.

MC 5403