For more information about this meeting, contact Stephen Simpson.
| Title: | LR-reducibility, LK-reducibility, and measure-theoretic regularity |
|---|
| Seminar: | Logic Seminar |
|---|
| Speaker: | Stephen G. Simpson, Pennsylvania State University |
|---|
| Abstract Link: | http://www.math.psu.edu/simpson/papers/aedsh.pdf |
|---|
| Abstract: |
|---|
| Let A and B be Turing oracles. We say that A is LR-reducible to B if every X which is random relative to B is random relative to A. We say that A is LK-reducible to B if K^B(tau) < K^A(tau) + O(1). Here K^A denotes prefix-free Kolmogorov complexity relative to A. Recently Kjos-Hanssen, Miller and Solomon discovered that LR-reducibility and LK-reducibility coincide. Moreover, A is LR-reducible to B if and only if every set of positive measure which is effectively closed relative to A includes a set of positive measure which is effectively closed relative to B. We sketch the proof of these and related results. |
Room Reservation Information
| Room Number: | MB315 |
|---|
| Date: | 09 / 22 / 2009 |
|---|
| Time: | 02:30pm - 03:45pm |
|---|
