For more information about this meeting, contact Stephen Simpson.
| Title: | Mass problems associated with effectively closed sets |
|---|
| Seminar: | Logic Seminar |
|---|
| Speaker: | Stephen G. Simpson, Pennsylvania State University |
|---|
| Abstract: |
|---|
| We examine some specific degrees of unsolvability of mass problems associated with nonempty effectively closed sets in the Cantor space. It is known that these degrees of unsolvability form a countable distributive lattice with 0 and 1. This lattice is known as P_w. We show that the top degree 1 in P_w is associated with the problem of finding a completion of an effectively essentially undecidable theory. We characterize 1 abstractly up to recursive homeomorphism and up to Turing equivalence, in terms of properties of effectively closed sets. We also consider a certain degree r in P_w which is intermediate between 0 and 1. We characterize r as the degree of the problem of finding an infinite sequence of head and tails which is random in the sense of Martin-Loef. Alternatively, we characterize r as the maximum degree of an effectively closed set of positive measure. As time permits we shall exhibit other interesting examples of specific, natural degrees in P_w. |
Room Reservation Information
| Room Number: | MB106 |
|---|
| Date: | 11 / 06 / 2007 |
|---|
| Time: | 02:30pm - 03:45pm |
|---|
