For more information about this meeting, contact Stephen Simpson, Jan Reimann.
|Title:||Compressibility and arithmetic.|
|Speaker:||Keita Yokoyama, Tokyo Institute of Technology|
|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
|Date:||05 / 29 / 2012|
|Time:||02:30pm - 03:45pm|