For more information about this meeting, contact Stephen Simpson, Jan Reimann.
| Title: | Compressibility and arithmetic. |
|---|
| Seminar: | Logic Seminar |
|---|
| Speaker: | Keita Yokoyama, Tokyo Institute of Technology |
|---|
| Abstract: |
|---|
| In this talk, I will introduce a compressibility notion in arithmetic,
and show the following:
Let K be the prefix-free complexity or the a priori complexity, and f
be an order function.
Then, a real X is not K-f-compressible in any recursive extension of
PA if and only if it is K-f-complex relative to some PA-degree.
Here, the latter condition is equivalent to X being strong-f-random,
so this gives a new characterization of strong-f-randomness.
This is a joint work with Higuchi, Hudelson and Simpson. |
Room Reservation Information
| Room Number: | MB315 |
|---|
| Date: | 05 / 29 / 2012 |
|---|
| Time: | 02:30pm - 03:45pm |
|---|
