Midwest Computability Seminar

XVI


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.

DATE: Tuesday, February 17th, 2015.
PLACE: Eckhart and Ryerson Halls, The University of Chicago (see below for rooms).
5734 S. University Ave., Chicago, IL 60637.


Speakers:

Schedule:


Abstracts:

Carl Jockusch

Title: Numerical levels of imperfect computability and Turing degrees

Abstract: I will mostly discuss joint work with Denis Hirschfeldt, Tim McNicholl, and Paul Schupp, and, separately, with Uri Andrews, Minghzhong Cai, David Diamondstone, and Steffen Lempp. We consider two types of imperfect algorithms, one of which never lies but may diverge on some arguments, and the other of which is total but may give some incorrect answers. These considerations lead to an assignment of real numbers α(A) and γ(A) in the unit interval to each subset A of ω, where these numbers, roughly speaking, give the lower density of the set of arguments where each type of imperfect algorithm gives the correct answer. (More precisely, they are the sups of such lower densities over all algorithms.) We study the relationship between α(A) and γ(A), the values they take on, and their connections with the Turing degree of A.


Julia Knight

Title : Computability and uncountable structures

Abstract: Using a notion defined by Noah Schweber, we can compare the computing power of uncountable structures. In joint work with Greg Igusa and Noah Schweber, Schweber's notion is applied to some structures related to the reals. A structure that simply gives the subsets of ω is strictly less powerful than the ordered field of real numbers. If we add to the ordered field of reals the exponential function, or any analytic function, there is no increase in computing power. If we drop multiplication from the reals, keeping addition and the ordering, there is no loss in computing power.


Steffen Lempp

Title: Spectra of computable models of strongly minimal disintegrated theories

Abstract: By a theorem of Baldwin and Lachlan, for a strongly minimal (or more generally, an ℵ0-categorical) theory T, the countable models form an elementary chain M0 ≺ M1 ≺ ... ≺ Mω of length ω+1 (unless T is totally categorical, of course). The spectrum of computable models of such a theory T is then
SCM(T) = { α≤ω | Mα is computable }.
For a long time, only certain intervals of [0,ω] were known to be spectra; but at the same time, there was only a hyperarithmetical upper bound on them, leaving a huge gap in our understanding.

In this talk, I will restrict myself to strongly minimal disintegrated theories, where recent work has yielded strong negative results. Andrews and Medvedev were able to show that for such theories in a finite language, only the three known examples ∅, [0,ω] and {0} were possible spectra, using an effective reduction to a binary language. Subsequently, Andrews and I were able to show that in a (possibly infinite) binary language, there are exactly seven possible spectra, namely, in addition to the above also {1}, {0,1}, [1,ω] and {ω}. The main tool in our proof was an effective reduction to a rank-1 relational language.

Recently, we have been able to extend our results to give partial answers for ternary relational languages and also in particular of rank-1 languages in general, both with a finite bound on the arity and without such a bound.

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.