Midwest Computability Seminar


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.

: Tuesday, April 21st, 2009 
PLACE: Ryerson, University of Chicago.
1100 East 58th Street, Chicago, IL 60637.




Dan Turetsky - U. of Wisconsin.
Title: Dimension Level Sets in the Plane
Abstract: Every point in the plane can be assigned an effective dimension between 0 and 2, which represents the density of information in it.  Lutz and Weihrauch investigated the connectedness of the set of points of a given dimension and discovered that, somewhat counter-intuitively, the dimension 1 points seem to be the most important.  I will present some of their results, as well as my own which support this observation.

Julia Knight - U. of Notre Dame.
TitleDescribing free groups
This is joint work with Jacob Carson, Valentina Harizanov, Julia Knight, Karen Lange, Christina Maher, Charles McCoy, CSC, Andrei Morozov, Sara Quinn, and John Wallbaum.
Abstract: The free group of rank 1 is Abelian. The free groups of rank greater than 1 are non-Abelian, and by results of Sela (for which he won the most recent Karp prize), they all have the same elementary first-order theory. We consider computable infinitary descriptions. To see that a description is optimal, we look at the index set, hoping for a match in complexity. Working within the class of free groups, we can give an optimal description for each group. For example, we have a computable Π2-sentence that describes F2, distinguishing it from other free groups. The index set is m-complete Π02 within free groups. Therefore, our description is optimal. Working within the class of all groups, we have found optimal descriptions for all free groups except the one of infinite rank. We have a computable Π4 description for F, but we can only show that the index set for is Π03-hard. The reason for the gap is that we do not know how to describe the tuples that can be part of a basis. Group theorists have worked on this. We use group-theoretic results in our work so far. To go further, we need further group-theoretic results, and these seem to be unknown.

Ted Slaman - U. of California, Berkeley
Title: Degree Invariant Functions
Abstract:  We will discuss Martin's Conjecture for functions which are invariant with respect to Turing degree and Kechris's question of whether Turing equivalence is universal among countable Borel equivalence relations.  In a result jointly obtained with Montalban and Reimann, we will give a restriction on the possible ways by which Turing equivalence could be universal.

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.