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 two half hour talks and two 1-hour talks and a few hours to talk and collaborate with each other.  The seminar started in the fall of 2008.

: Tuesday, January 26th, 2010.
PLACE: Ryerson, University of Chicago.
1100 East 58th Street, Chicago, IL 60637.




Sara Quinn.
Title:  Turing Computable Embedding
Abstract:  The notion of a Turing computable embedding is an effective analogue of the Borel embeddings used in descriptive set theory to compare classes of countable structures.  The partial ordering that arises from this embedding notion allow us to order the complexity of the classification problem for various classes of structures.  In this talk I will discuss the background behind the notion, some interesting examples of embedding and non-embedding results, and some possible future directions of inquiry using this embedding. 

John Wallbaum.
Title: Primitive elements of free groups
Abstract: In this talk I will describe how Charlie McCoy and I were able to use recent results in group theory to show that the index set for F_{\infty}, the countably generated free group, is m-complete Pi^0_4. I will also mention our result that there is a computable copy of F_{\infty} with no Sigma^0_2 basis, which is sharp since every computable copy has a Pi^0_2 basis.

Steffen Lempp.
Comparing effective notions of categoricity.
Abstract: We compare computable categoricity and (relativized notions of) relative computable categoricity. It is easy to see that any relatively computably categorical model is computably categorical. Goncharov, using effective versions of Scott families, showed that the converse holds for 2-decidable models. On the other hand, Kudinov showed that the converse fails even for 1-decidable models.
  We extend these results by showing that (1) any 1-decidable computably categorical model is relatively Δ02-computably categorical; and (2) there is a computably categorical model which is not relatively arithmetically categorical.
  It is not hard to see, using Goncharov's characterization of relative computable categoricity and a simple construction, that this notion is Σ03-complete. The characterization of the complexity of computable categoricity remains open, and appears very hard in light of the second part of the above theorem; in fact, while it is trivially Π11, and Π04-hard by White, it is not even known whether computable categoricity is arithmetical or not.
  This is joint work with Downey, Kach and Turetsky.

Reed Solomon.
Title: Self-embeddings of computable trees
Abstract:  We present results concerning the complexity of self-embeddings for computable trees motivated by similar computability theoretic work in the context of the Dushnik-Miller Theorem for linear orders. This work is joint with Stephen Binns, Bjoern Kjos-Hanssen, Manny Lerman and Jim Schmerl.

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.