Midwest Computability Seminar

IV

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 Chicago.
1100 East 58th Street, Chicago, IL 60637.

Speakers:

Dan Turetsky - U. of Wisconsin.
Dimension Level Sets in the Plane
Julia Knight - U. of Notre Dame.
Describing free groups
Ted Slaman - U. of California, Berkeley
Degree Invariant Functions

Schedule:

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, IL 60608.
(Note that dinner is not in Hyde Park, but in Pilsen.)

Abstracts:

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.
Title: Describing 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 Π₂-sentence that describes F₂, distinguishing it from other free groups. The index set is m-complete Π⁰₂ 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 Π₄ description for F_∞, but we can only show that the index set for is Π⁰₃-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:

Sept 22nd 2009. (tentative)

2008/2009 Seminars:

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.