Cole Wyeth, University of Waterloo
Introduction to Prefix-free Kolmogorov Complexity
I will continue last week's introduction to algorithmic complexity by upgrading from the plain Kolmogorov complexity to the prefix-free Kolmogorov complexity, which offers a more effective explanation of effective explanations. This alternative formalization of algorithmic complexity can be motivated in terms of probabilistic programs with "random seeds." I will explain why the probabilistic approach might be considered heretical (by Kolmogorov), and prove some slightly more sophisticated properties of the prefix-free Kolmogorov complexity. As time permits, I will also define its conditional version, which has been used to construct the information distance and its practical counterpart, the normalized compression distance, which was applied to bioninformatics by my advisor Professor Ming Li.
MC 5403