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