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

Carl
Jockusch  University of Illinois at UrbanaChampaign
 Julia Knight  Notre Dame
 Steffen Lempp  Wisconsin
Schedule:
 12:30  1:30: Lunch in Ryerson 255 (note the change from our
usual room)
 1:30  2:20: Steffen Lempp in Eckhart 206
 3:00  3:50: Julia Knight in Eckhart 206
 4:30  5:20: Carl Jockusch in Eckhart 202
 6:00: Dinner at The Nile, 1162 East 55th Street
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 M_{0} ≺ M_{1}
≺ ... ≺ 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 rank1 relational language.
Recently, we have been able to extend our results to give partial answers
for
ternary relational languages and also in particular of rank1 languages
in general, both with a finite bound on the arity and without such a
bound.
Previous 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
 Sept 29th 2009. Carl Jockusch
 Rachel Epstein  Rebecca Weber
 Jan 26th 2010. Sara Quinn 
John Wallbaum  Steffen Lempp  Reed Solomon
 May 11th 2010. Adam Day 
Liang Yu  Rod Downey  Boris Zilber
 Sept 28th 2010. Maurice
Chiodo  Peter Gerdes  Damir Dzhafarov  Andy Lewis
 Feb 15th 2011. Uri Andrews 
Paola D'Aquino  David Diamondstone  Christopher Porter 
Rebecca Steiner.
 Nov 1st 2011. Mingzhong Cai 
Chris Conidis  Stephen Flood 
Jeff Hirst  Asher Kach.
 Nov 15th 2012 Achilles Beros
 Rod Downey  Jesse Johnson  Sam Sanders  Steven VanDendriessche 
Matthew Wright.
 April 2nd 2013 Howard
Becker  Denis Hirschfeldt  Paul Schupp.
 October 1st 2013 Peter Cholak
 Mushfeq Khan  Victor OcasioGonzález  Jonathan Stephenson
 April 29th, 2014 Rod Downey 
Noam Greenberg  Gregory Igusa  Alexander Melnikov  Kyle Riggs
 September 30th, 2014 Eric Astor 
Quinn Culver  Jack Lutz  Timothy McNicholl
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.