PSU Mark
Eberly College of Science Mathematics Department

Meeting Details

For more information about this meeting, contact Stephen Simpson.

Title:The power of random strings
Seminar:Logic Seminar
Speaker:Adam Day, Victoria University of Wellington, New Zealand
Abstract:
Kolmogorov complexity provides a means of measuring the information content of a string. There are different types of Kolmogorov complexity and in this talk we will review three of them: plain Kolmogorov complexity, prefix-free Kolmogorov complexity, and a priori probability. Any type of Kolmogorov complexity gives rise to two fundamental computably enumerable sets. These are the set of non-random strings and the overgraph. We will investigate the computational power of these sets. We will review work done by Kummer, Muchnik and Positselsky, and Allender and co-authors who have examined the computational power of these sets for plain and prefix-free Kolmogorov complexity. We will also discuss the complexity of the overgraph for a priori probability.

Room Reservation Information

Room Number:MB315
Date:12 / 07 / 2010
Time:02:30pm - 03:45pm