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, April 21st, 2009
PLACE: Ryerson, University of
1100 East 58th Street, Chicago, IL 60637.
- Dan Turetsky - U. of Wisconsin.
Sets in the Plane
- Julia Knight - U. of Notre Dame.
Describing free groups
- Ted Slaman - U. of California, Berkeley
- Noon: Lunch at Ryerson 255 (the coffee room).
- 12:50 - 1:40: Dan Turetsky (Ry 251).
- 2:10 - 3:00: Julia Knight (Ry 251).
- 3:00 - 4:30: Coffee break (Ry 255).
- 4:30 - 5:20: Ted Slaman (Ry 277).
- 6:30pm: Dinner. Nuevo Leon Restaurant, 1515 W 18th St, Chicago,
(Note that dinner is not in Hyde Park, but in Pilsen.)
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
Julia Knight - U. of Notre
Title: Describing free groups
This is joint work with Jacob Carson, Valentina Harizanov, Julia
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
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
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,
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
- Sept 22nd 2009. (tentative)
- Sept 23th 2008. Antonio
Montalbán - Logan Axon - Joe Miller
- Nov 11th 2008. Chris
Conidis - Keng Meng (Selwyn) Ng - Peter Gerdes
- Feb 3rd 2009. David Diamondstone
- Bart Kastermans - Richard A. Shore
- April 21th 2009. Dan Turetsky - Julia Knight - Ted Slaman
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.