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 |