PSU Mark
Eberly College of Science Mathematics Department

Meeting Details

For more information about this meeting, contact Jan Reimann, Stephen Simpson.

Title:Degree of Randomness versus Turing degree
Seminar:Logic Seminar
Speaker:William Calhoun, Bloomsburg University
Abstract:
The degree of randomness of a real x can be defined in terms of the prefix-free or montone Kolmogorov complexity of initial segments of x. The Turing degree of x is defined quite differently in terms of the relative computability of x. At first glace there is little connection between the Turing degree and the degree of randomness. However, there are relationships between the two notions. In the prefix-free complexity setting, the reals with the lowest degree of randomness are called the K-trivial reals. Nies has shown that K-trivial reals have limited power as oracles. In the montone complexity setting, the situation is quite different and there are some interesting open questions.

Room Reservation Information

Room Number:MB315
Date:02 / 21 / 2012
Time:02:30pm - 03:45pm