PSU Mark
Eberly College of Science Mathematics Department

Meeting Details

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