Midwest Computability Seminar

XVIII

Special Meeting in Honor of Carl Jockusch's 75th Birthday


The Midwest Computability Seminar is a joint venture between the University of Chicago, the University of Notre Dame, and the University of Wisconsin-Madison. It meets once or twice per semester at the University of Chicago, and is attended by faculty and students from these universities and others in the area. The seminar started in the fall of 2008.

We are holding a special meeting to honor Carl Jockusch's exceptional and fundamental contributions to computability theory in general and the Midwest logic community in particular.

DATES: Saturday and Sunday, October 22-23, 2016.
PLACE: Ryerson Hall 352 (the Barn) and Eckhart Hall 206, The University of Chicago.


Organizers:
Speakers:      

Schedule: All talks and coffee breaks will be in Ryerson 352 (the Barn), except as noted.

Saturday, October 22nd
Sunday, October 23rd

Titles and Abstracts:

Eric Astor

Title: Letting the Natural Numbers Vote (or, Upper Cones for Asymptotic Computation)

Abstract: It is well-known that upper cones for Turing computation have measure 0... or, in other words, that any set that is computable from "any meaningful fraction of sets X" is just plain computable. Turning to asymptotic computability (the study of which was introduced in a collaboration between Carl Jockusch and Paul Schupp), we introduce two new variations on asymptotic computation, and then show that the same fact is true for all four variations - anything that is "usually computable" relative to too many sets X is in fact just "usually computable". To prove this, we provide a weak version of Fubini's Theorem for asymptotic density, which allows us to use a form of majority-rule voting over the set of natural numbers. This is joint work with Denis Hirschfeldt and Carl Jockusch.


Damir Dzhafarov

Title: Ramsey's Theorem and Products in the Weihrauch Degrees

Abstract: One of Carl Jockusch's seminal contributions to computability theory was his 1972 paper on Ramsey's theorem, which spawned an industry of research into computable combinatorics, and gave rise to one of the most active and fruitful areas of study in reverse mathematics. Ramsey's theorem for pairs, RT(2), has proven to be a particularly rich source of questions in this area. A recent focus has been to try to understand RT(2) using the tools of computable reducibility and Weihrauch reducibility, which can be regarded as extending and refining the traditional framework of reverse mathematics. Much of this work has focused on teasing apart differences between variants of RT(2) that are either undetectable in the traditional framework of provability over RCA0, or unknown and seemingly more difficult to resolve. Two important such variants are the stable Ramsey's theorem for pairs, SRT(2), and the cohesive principle, COH. It was shown by Cholak, Jockusch, and Slaman that RT(2) is equivalent over RCA0 to SRT(2) + COH. Brattka and Rakotoniania noticed that one direction of this equivalence can be expressed in terms of the so-called compositional product, *, in the Weihrauch lattice: namely, RT(2) is Weihrauch reducible to SRT(2) * COH. In turn, they asked whether the reverse reduction also holds. Surprisingly, the answer turns out to be no: RT(2) is strictly weaker than SRT(2) * COH, so the uniform power of constructions involving one application of COH followed by one application of SRT(2) is strictly greater than the uniform power of RT(2) alone. I will give an overview of the proof of this result, along with a brief survey of the growing role of Weihrauch reducibility for studying combinatorial principles. This is joint work with Hirschfeldt, Patey, and Pauly.


Denis Hirschfeldt

Title: Notions of Computability-Theoretic Reducibility between Π12 Principles

Abstract: I will discuss computable reducibility, Weihrauch reducibility, and some other notions of computability-theoretic reducibility between mathematical principles, including ones introduced in a recent joint paper with Carl, focusing in particular on Ramsey-theoretic principles.


Julia Knight

Title: Lengths of Roots of Polynomials in a Hahn Field (joint work with Karen Lange)

Abstract: For a divisible ordered Abelian group G, and a field K, the Hahn field K((G)) consists of generalized power series with terms corresponding to elements of a well ordered subset of G and coefficients in K. Maclane showed that for a divisible ordered Abelian group G, and a field K that is algebraically closed, or real closed, the Hahn field K((G)) is also algebraically closed, or real closed. The ideas for finding roots go back to Newton and Puiseux. For an element r = ∑g ∈ S agtg of K((G)), the support is the set of g ∈ G with ag ≠ 0, and the length is the order type of the support. We can bound the length of a root of a polynomial in terms of the lengths of the coefficients. For a "truncation closed subfield" R of K((G)), we can bound the lengths of elements of R in terms of the length of a sequence forming a "truncation closed" transcendence basis. This work is algebraic, although our motivation came from computability. Now, we want to return to computability. We need a good way to represent elements of a Hahn field, so that we can measure the complexity of the root-taking process.


Joe Mileti

Title: Reflections on Carl as a Researcher, Teacher, and Adviser


Ludovic Patey

Title: Coloring Trees in Reverse Mathematics

Abstract: The tree theorem asserts that given a finite coloring of pairs of comparable nodes in the full binary tree 2<ω, there is a set of nodes isomorphic to 2<ω which is homogeneous for the coloring. In this talk, we will give an overview of the known literature about the reverse mathematics of the tree theorem for pairs, started by Chubb, Hirst, and McNicholl. We will in particular present the recent proof that the tree theorem for pairs does not imply ACA in RCA. This is a joint work with Damir Dzhafarov.


Paul Schupp

Title: Reflections on Asymptotic Density and Computability

Abstract: Following the recent survey of the development of generic and coarse computability by Carl Jockusch and myself, I will try to outline the subject and make some comments on the general idea of the overall goal.


Ted Slaman

Title: Scott Sets and Turing Degrees

Abstract: In the 1970's Jockusch and Soare laid the foundation for the study of the Turing degrees of elements of Π01-classes. We will review how this study has evolved, state what is known, describe the associated mathematical technology, and speculate on what might be true for the Turing degress of an arbitrary Scott set.


Robert Soare

Title: Fifty Years With Carl

Abstract: I first met Carl exactly fifty years ago at a meeting at Cornell in May, 1966 when we were both finishing our Ph.D. theses. We discovered we were working on similar topics. A year later we both moved to Illinois, Carl to UIUC and I to UIC. Our collaboration began then on a number of topics and continued over the next decades. I will describe some of the anecdotes and memories of my time with Carl with only a brief hint at the mathematics, but with the emphasis on the memories.


Linda Brown Westrick

Title: Dimension 1 Sequences Are Close to Randoms

Abstract: We give another answer to the informal question: are sequences of effective Hausdorff dimension 1 just random sequences that have been "messed up"? We show that a sequence has effective Hausdorff dimension 1 if and only if it differs from a Martin-Löf random sequence on a set of density zero. The proof makes essential use of Harper's Theorem concerning finite combinatorics of Hamming spheres. We also ask and answer similar questions for sequences of effective dimension s<1. This is joint work with J. Miller, N. Greenberg, and A. Shen.



We have reserved blocks of rooms at two local hotels, LaQuinta Inn & Suites and the Chicago Lake Shore Hotel, for the nights of Oct. 21st and 22nd. These are adjacent to each other and under the same management, but have separate reservation numbers. In both cases, the rooms are under "Midwest Computability Seminar" and will be held until September 15th (so please book as soon as possible, since local hotel availability is quite limited). The rates we have been quoted and the phone numbers are as follows (when calling, ask for reservations):

LaQuinta Inn & Suites:
$149+tax / night
773-324-3000

Chicago Lake Shore Hotel:
$119+tax / night
773-288-5800

Previous Seminars:

If you haven't been receiving the announcements and would like to be included in the list, send an email to drh@math.uchicago.edu.