Logic Seminar
Gregory Igusa
University of Notre Dame
Turing Filters and Ideals in the Generic Degrees
Abstract: We say that a real, $A$, is generically computable if there is a partial computable function $\phi$ which correctly computes the majority of the bits of $A$, and never gives any incorrect outputs. (So dom$(\phi)$ is a subset of $\omega$ with asymptotic density 1.) The terminology and motivation for this are derived from recent work in complexity theory which studies the ``generic-case complexity" of a problem which might, in principle, be much easier in the generic case than in the worst case.
If we wish to relativize generic computability to study its degree structure, we are forced to work with uncountable collections of partial oracles for each real: any computation that halts on density 1 is an acceptable generic computation, and so any oracle that answers density-1 many questions must be an acceptable generic oracle. This produces a $\bf{\Pi}^1_1$-complete reducibility that is somewhat difficult to work with.
The Turing degrees embed naturally into the generic degrees, and this provides a very useful perspective from which to view the generic degrees. Given a generic degree, we may consider the Turing ideal or filter of Turing degrees that embed below or above it. We present some results about what sorts of ideals and filters can be realized in this manner, and we also provide a characterization of the hyperarithmetic sets in terms of generic reduction and coarse computability, a closely-related notion of computability.
Tuesday February 11, 2014 at 4:00 PM in SEO 427