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:

- Carl Jockusch - U. of Illinois at Urbana-Champaign

- Rachel Epstein - U. of Chicago.

- Rebecca Weber - Dartmouth College.

- 12:00 - 1:00: Lunch. (the Barn Ry 352)
- 1:00 - 2:00: Carl Jockusch (the Barn Ry 352).

- 2:00 - 3:00: Coffee break (Ry 255).
- 3:00 - 4:00: Rachel Epstein (Ry 251).

- 4:00 - 4:30: Coffee break (Ry 255).
- 4:30 - 5:30: Rebecca Weber (Ry 251).

- 6pm: Dinner. Chicago Curry House, 899
S. Plymouth Ct

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

We say a class of c.e. degrees is

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.

- Sept 29th 2009.

- 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.