PSU Mark
Eberly College of Science Mathematics Department

Meeting Details

For more information about this meeting, contact Stephen Simpson.

Title:Tests for partial randomness
Seminar:Logic Seminar
Speaker:Stephen G. Simpson, Pennsylvania State University
Abstract:
Let f be a computable convex order function, for example f(n) = n/2, or f(n) = the square root of n, or f(n) = log n. A infinite sequence of 0's and 1's is said to be f-complex if the prefix-free complexity of the first n bits exceeds KP(n) - O(1) where KP denotes prefix-free Kolmogorov complexity. Replacing KP by a priori complexity, KA, we obtain strong f-randomness. The purpose of this talk is to present alternative characterizations of f-complexity and strong f-complexity, using "randomness tests" in the style of Martin-L"of. If time permits, we shall sketch the proofs of some new results concerning strong f-randomness relative to a Turing oracle.

Room Reservation Information

Room Number:MB315
Date:07 / 05 / 2011
Time:09:45am - 11:00am