Midwest Computability Seminar

V


The Midwest Computability Seminar meets twice in the fall and twice in the spring at University of Chicago.  Researchers in computability theory and their students and postdocs from University of Chicago, University of Notre Dame, and University of Wisconsin-Madison plus some others throughout the area regularly attend. Normally we have three 1-hour talks and a few hours to talk and collaborate with each other.  The seminar started in the fall of 2008.

DATE: Tuesday, September 29th, 2009 
PLACE: Ryerson, University of Chicago.
1100 East 58th Street, Chicago, IL 60637.


Speakers:

Schedule:

Abstracts:

Speaker:  Carl Jockusch
Title: The relative difficulty of bounded diagonalization and randomization
Abstract:
 I will discuss recent joint work with Rod Downey, Noam Greenberg, and Kevin Milans.  We show that the class of Kurtz-random sets is not strongly (or Medvedev) reducible to DNR_3 , the class of diagonally noncomputable functions taking values in {0,1,2}.  This means that there is no fixed oracle Turing machine which, given any function in DNR_3 as an oracle, computes a set which is not an element of any null Pi01 class (with respect to the usual measure on Cantor space).  The key element of the proof is a new Ramseyan result on rooted ternary trees with certain edges having labels in {0,1}.  Here the goal is to obtain appropriate perfect binary branching subtrees with few labels occurring along paths.  In fact we obtain a family of related combinatorial results on this topic.  Our main result (stated above) may be combined with known results to show that, under strong reducibility, DNR_3 and the family of Kurtz-random sets are incomparable and strictly below DNR_2.

Speaker:  Rachel Epstein.
Title: Invariance and Automorphisms.
Abstract:
  The class of computably enumerable (c.e.) sets forms a lattice E under inclusion. We say a class of c.e. degrees is definable if it is the set of degrees of a class of c.e. sets that is definable in the language of inclusion. For example, the high degrees are definable because they are exactly the degrees of maximal sets, as Martin has shown.
  We say a class of c.e. degrees is invariant if it is the set of degrees of a class of c.e. sets that is invariant under automorphisms of E. Since the high degrees are definable, they are also invariant. Mathematicians have studied the definability and invariance of degree classes, particularly the jump classes of degrees, L_n, H_n, and their complements.
  All jump classes have been previously classified as invariant or noninvariant, except for the nonlow_1 degrees. We show that the nonlow_1 degrees are noninvariant and thus not definable, making this the only upward-closed jump class that is noninvariant.

Speaker: Rebecca Weber.
Ttitle: Degree invariance in the Pi^0_1 classes
Abstract:
  Degree invariance is a connection between the algebraic properties of a structure and the computability-theoretic properties of its elements, and a way to argue for the naturality of a collection of degrees.  Recently, Cholak and Harrington proved a large definability result that gives, as a corollary, the degree invariance over the c.e. sets of the high_n and non-low_n degrees for n > 1.  I have translated that result to another structure which gives the same corollary over the Pi^0_1 classes.  Previously only one degree class (the array noncomputable degrees) was known to be invariant over the Pi^0_1 classes.  In this talk I will discuss degree invariance in general, give a high-level overview of the proof, and discuss the changes and background material required for the new structure.


2009/2010 Seminars:
2008/2009 Seminars:
   If you haven't been receiving the announcements, and you would like to be included in the list, send me an email to antonio at uchicago.edu.