For more information about this meeting, contact Stephen Simpson.
|Title:||Tests for partial randomness|
|Speaker:||Stephen G. Simpson, Pennsylvania State University|
|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
|Date:||07 / 05 / 2011|
|Time:||09:45am - 11:00am|