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 |
|---|
